← Back to branch summary

~ubuntu-branches/ubuntu/maverick/strongswan/maverick

« back to all changes in this revision

Viewing changes to src/charon/credentials/sets/cert_cache.c

  • Committer: Bazaar Package Importer
  • Author(s): Rene Mayrhofer
  • Date: 2009-04-01 22:17:52 UTC
  • mfrom: (1.1.8 upstream)
  • Revision ID: james.westby@ubuntu.com-20090401221752-eozrk0ctabblo94z
http://bugs.debian.org/521950
* New upstream release, which incorporates the fix. Removed dpatch for it.
  Closes: #521950: CVE-2009-0790: DoS
* New support for EAP RADIUS authentication, enabled for this package.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/charon/credentials/sets/cert_cache.c
18
18
#include "cert_cache.h"
19
19
 
20
20
#include <time.h>
 
21
#include <sched.h>
21
22
 
22
23
#include <daemon.h>
23
24
#include <utils/mutex.h>
24
25
#include <utils/linked_list.h>
25
26
 
26
 
#define CACHE_SIZE 30
 
27
/** cache size, a power of 2 for fast modulo */
 
28
#define CACHE_SIZE 32
 
29
 
 
30
/** attempts to acquire a cache lock */
 
31
#define REPLACE_TRIES 5
27
32
 
28
33
typedef struct private_cert_cache_t private_cert_cache_t;
29
34
typedef struct relation_t relation_t;
30
35
 
31
36
/**
 
37
 * A trusted relation between subject and issuer
 
38
 */
 
39
struct relation_t {
 
40
        
 
41
        /**
 
42
         * subject of this relation
 
43
         */
 
44
        certificate_t *subject;
 
45
        
 
46
        /**
 
47
         * issuer of this relation
 
48
         */
 
49
        certificate_t *issuer;
 
50
        
 
51
        /**
 
52
         * Cache hits
 
53
         */
 
54
        u_int hits;
 
55
        
 
56
        /**
 
57
         * Lock for this relation
 
58
         */
 
59
        rwlock_t *lock;
 
60
};
 
61
 
 
62
/**
32
63
 * private data of cert_cache
33
64
 */
34
65
struct private_cert_cache_t {
35
 
 
 
66
        
36
67
        /**
37
68
         * public functions
38
69
         */
39
70
        cert_cache_t public;
40
71
        
41
72
        /**
42
 
         * list of trusted subject-issuer relations, as relation_t
43
 
         */
44
 
        linked_list_t *relations;
45
 
        
46
 
        /**
47
 
         * do we have an active enumerator
48
 
         */
49
 
        refcount_t enumerating;
50
 
        
51
 
        /**
52
 
         * have we increased the cache without a check_cache?
53
 
         */
54
 
        bool check_required;
55
 
        
56
 
        /**
57
 
         * read-write lock to sets list
58
 
         */
59
 
        rwlock_t *lock;
60
 
};
61
 
 
62
 
/**
63
 
 * A trusted relation between subject and issuer
64
 
 */
65
 
struct relation_t {
66
 
        /** subject of this relation */
67
 
        certificate_t *subject;
68
 
        /** issuer of this relation */
69
 
        certificate_t *issuer;
70
 
        /** time of last use */
71
 
        time_t last_use;
72
 
};
73
 
 
74
 
/**
75
 
 * destroy a relation_t structure
76
 
 */
77
 
static void relation_destroy(relation_t *this)
78
 
{
79
 
        this->subject->destroy(this->subject);
80
 
        this->issuer->destroy(this->issuer);
81
 
        free(this);
82
 
}
83
 
 
84
 
/**
85
 
 * check the cache for oversize
86
 
 */
87
 
static void check_cache(private_cert_cache_t *this)
88
 
{
89
 
        if (this->enumerating)
 
73
         * array of trusted subject-issuer relations
 
74
         */
 
75
        relation_t relations[CACHE_SIZE];
 
76
};
 
77
 
 
78
/**
 
79
 * Cache relation in a free slot/replace an other
 
80
 */
 
81
static void cache(private_cert_cache_t *this,
 
82
                                  certificate_t *subject, certificate_t *issuer)
 
83
{
 
84
        relation_t *rel;
 
85
        int i, offset, try;
 
86
        u_int total_hits = 0;
 
87
        
 
88
        /* check for a unused relation slot first */
 
89
        for (i = 0; i < CACHE_SIZE; i++)
90
90
        {
91
 
                this->check_required = TRUE;
 
91
                rel = &this->relations[i];
 
92
                
 
93
                if (!rel->subject && rel->lock->try_write_lock(rel->lock))
 
94
                {
 
95
                        /* double-check having lock */
 
96
                        if (!rel->subject)
 
97
                        {
 
98
                                rel->subject = subject->get_ref(subject);
 
99
                                rel->issuer = issuer->get_ref(issuer);
 
100
                                return rel->lock->unlock(rel->lock);
 
101
                        }
 
102
                        rel->lock->unlock(rel->lock);
 
103
                }
 
104
                total_hits += rel->hits;
92
105
        }
93
 
        else if (this->lock->try_write_lock(this->lock))
94
 
        {       /* never blocks, only done if lock is available */
95
 
                while (this->relations->get_count(this->relations) > CACHE_SIZE)
 
106
        /* run several attempts to replace a random slot, never block. */
 
107
        for (try = 0; try < REPLACE_TRIES; try++)
 
108
        {
 
109
                /* replace a random relation */
 
110
                offset = random();
 
111
                for (i = 0; i < CACHE_SIZE; i++)
96
112
                {
97
 
                        relation_t *oldest = NULL, *current;
98
 
                        enumerator_t *enumerator;
 
113
                        rel = &this->relations[(i + offset) % CACHE_SIZE];
99
114
                        
100
 
                        enumerator = this->relations->create_enumerator(this->relations);
101
 
                        while (enumerator->enumerate(enumerator, &current))
 
115
                        if (rel->hits > total_hits / CACHE_SIZE)
 
116
                        {       /* skip often used slots */
 
117
                                continue;
 
118
                        }
 
119
                        if (rel->lock->try_write_lock(rel->lock))
102
120
                        {
103
 
                                if (oldest == NULL || oldest->last_use <= current->last_use)
 
121
                                if (rel->subject)
104
122
                                {
105
 
                                        oldest = current;
 
123
                                        rel->subject->destroy(rel->subject);
 
124
                                        rel->issuer->destroy(rel->issuer);
106
125
                                }
 
126
                                rel->subject = subject->get_ref(subject);
 
127
                                rel->issuer = issuer->get_ref(issuer);
 
128
                                rel->hits = 0;
 
129
                                return rel->lock->unlock(rel->lock);
107
130
                        }
108
 
                        enumerator->destroy(enumerator);
109
 
                        this->relations->remove(this->relations, oldest, NULL);
110
 
                        relation_destroy(oldest);
111
131
                }
112
 
                this->check_required = FALSE;
113
 
                this->lock->unlock(this->lock);
 
132
                /* give other threads a chance to release locks */
 
133
                sched_yield();
114
134
        }
115
135
}
116
136
 
121
141
                                          certificate_t *subject, certificate_t *issuer)
122
142
{
123
143
        relation_t *found = NULL, *current;
124
 
        enumerator_t *enumerator;
 
144
        int i;
125
145
        
126
 
        /* lookup cache */
127
 
        this->lock->read_lock(this->lock);
128
 
        enumerator = this->relations->create_enumerator(this->relations);
129
 
        while (enumerator->enumerate(enumerator, &current))
 
146
        for (i = 0; i < CACHE_SIZE; i++)
130
147
        {
131
 
                bool match = FALSE;
132
 
        
133
 
                /* check for equal certificates */
134
 
                if (subject->equals(subject, current->subject))
135
 
                {
136
 
                        match = TRUE;
137
 
                        subject = current->subject;
138
 
                }
139
 
                if (issuer->equals(issuer, current->issuer))
140
 
                {
141
 
                        issuer = current->issuer;
142
 
                        /* if both certs match, we already have a relation */
143
 
                        if (match)
 
148
                current = &this->relations[i];
 
149
                
 
150
                current->lock->read_lock(current->lock);
 
151
                if (current->subject)
 
152
                {
 
153
                        /* check for equal issuer */
 
154
                        if (issuer->equals(issuer, current->issuer))
144
155
                        {
145
 
                                current->last_use = time(NULL);
146
 
                                found = current;
147
 
                                break;
 
156
                                /* reuse issuer instance in cache() */
 
157
                                issuer = current->issuer;
 
158
                                if (subject->equals(subject, current->subject))
 
159
                                {
 
160
                                        /* write hit counter is not locked, but not critical */
 
161
                                        current->hits++;
 
162
                                        found = current;
 
163
                                }
148
164
                        }
149
165
                }
 
166
                current->lock->unlock(current->lock);
 
167
                if (found)
 
168
                {
 
169
                        return TRUE;
 
170
                }
150
171
        }
151
 
        enumerator->destroy(enumerator);
152
 
        this->lock->unlock(this->lock);
153
 
        if (found)
 
172
        /* no cache hit, check and cache signature */
 
173
        if (subject->issued_by(subject, issuer))
154
174
        {
 
175
                cache(this, subject, issuer);
155
176
                return TRUE;
156
177
        }
157
 
        /* no cache hit, check signature */
158
 
        if (!subject->issued_by(subject, issuer))
159
 
        {
160
 
                return FALSE;
161
 
        }
162
 
        /* cache if good, respect cache limit */
163
 
        found = malloc_thing(relation_t);
164
 
        found->subject = subject->get_ref(subject);
165
 
        found->issuer = issuer->get_ref(issuer);
166
 
        found->last_use = time(NULL);
167
 
        /* insert should be ok without lock */
168
 
        this->relations->insert_last(this->relations, found);
169
 
        check_cache(this);
170
 
        return TRUE;
 
178
        return FALSE;
171
179
}
172
180
 
173
181
/**
174
 
 * data associated to a cert enumeration 
 
182
 * certificate enumerator implemenation
175
183
 */
176
184
typedef struct {
 
185
        /** implements enumerator_t interface */
 
186
        enumerator_t public;
177
187
        /** type of requested certificate */
178
188
        certificate_type_t cert;
179
189
        /** type of requested key */
180
190
        key_type_t key;
181
 
        /** ID to get a cert from */
 
191
        /** ID to get a cert for */
182
192
        identification_t *id;
183
 
        /** reverse pointer to cache */
184
 
        private_cert_cache_t *this;
185
 
} cert_data_t;
 
193
        /** cache */
 
194
        relation_t *relations;
 
195
        /** current position in array cache */
 
196
        int index;
 
197
        /** currently locked relation */
 
198
        int locked;
 
199
} cert_enumerator_t;
186
200
 
187
201
/**
188
202
 * filter function for certs enumerator
189
203
 */
190
 
static bool certs_filter(cert_data_t *data, relation_t **in, certificate_t **out)
 
204
static bool cert_enumerate(cert_enumerator_t *this, certificate_t **out)
191
205
{
192
206
        public_key_t *public;
193
 
        certificate_t *cert;
 
207
        relation_t *rel;
194
208
        
195
 
        cert = (*in)->subject;
196
 
        if (data->key == KEY_ANY && data->id && 
197
 
                (data->cert == CERT_ANY || data->cert == CERT_X509_CRL) &&
198
 
                cert->get_type(cert) == CERT_X509_CRL)
199
 
        {       /* CRL lookup is done using issuer/authkeyidentifier */
200
 
                if (cert->has_issuer(cert, data->id))
201
 
                {
202
 
                        *out = cert;
203
 
                        return TRUE;
204
 
                }
 
209
        if (this->locked >= 0)
 
210
        {
 
211
                rel = &this->relations[this->locked];
 
212
                rel->lock->unlock(rel->lock);
 
213
                this->locked = -1;
205
214
        }
206
215
        
207
 
        if ((data->cert == CERT_ANY || cert->get_type(cert) == data->cert) &&
208
 
                (!data->id || cert->has_subject(cert, data->id)))
 
216
        while (++this->index < CACHE_SIZE)
209
217
        {
210
 
                if (data->key == KEY_ANY)
211
 
                {
212
 
                        *out = cert;
213
 
                        return TRUE;
214
 
                }
215
 
                public = cert->get_public_key(cert);
216
 
                if (public)
217
 
                {
218
 
                        if (public->get_type(public) == data->key)
 
218
                rel = &this->relations[this->index];
 
219
                rel->lock->read_lock(rel->lock);
 
220
                this->locked = this->index;
 
221
                if (rel->subject)
 
222
                {
 
223
                        /* CRL lookup is done using issuer/authkeyidentifier */
 
224
                        if (this->key == KEY_ANY && this->id && 
 
225
                                (this->cert == CERT_ANY || this->cert == CERT_X509_CRL) &&
 
226
                                rel->subject->get_type(rel->subject) == CERT_X509_CRL &&
 
227
                                rel->subject->has_issuer(rel->subject, this->id))
219
228
                        {
220
 
                                public->destroy(public);
221
 
                                *out = cert;
 
229
                                *out = rel->subject;
222
230
                                return TRUE;
223
231
                        }
224
 
                        public->destroy(public);
 
232
                        if ((this->cert == CERT_ANY ||
 
233
                                 rel->subject->get_type(rel->subject) == this->cert) &&
 
234
                                (!this->id || rel->subject->has_subject(rel->subject, this->id)))
 
235
                        {
 
236
                                if (this->key == KEY_ANY)
 
237
                                {
 
238
                                        *out = rel->subject;
 
239
                                        return TRUE;
 
240
                                }
 
241
                                public = rel->subject->get_public_key(rel->subject);
 
242
                                if (public)
 
243
                                {
 
244
                                        if (public->get_type(public) == this->key)
 
245
                                        {
 
246
                                                public->destroy(public);
 
247
                                                *out = rel->subject;
 
248
                                                return TRUE;
 
249
                                        }
 
250
                                        public->destroy(public);
 
251
                                }
 
252
                        }
225
253
                }
 
254
                this->locked = -1;
 
255
                rel->lock->unlock(rel->lock);
226
256
        }
227
257
        return FALSE;
228
258
}
230
260
/**
231
261
 * clean up enumeration data
232
262
 */
233
 
static void certs_destroy(cert_data_t *data)
 
263
static void cert_enumerator_destroy(cert_enumerator_t *this)
234
264
{
235
 
        ref_put(&data->this->enumerating);
236
 
        data->this->lock->unlock(data->this->lock);
237
 
        if (data->this->check_required)
 
265
        relation_t *rel;
 
266
        
 
267
        if (this->locked >= 0)
238
268
        {
239
 
                check_cache(data->this);
 
269
                rel = &this->relations[this->locked];
 
270
                rel->lock->unlock(rel->lock);
240
271
        }
241
 
        free(data);
 
272
        free(this);
242
273
}
243
274
 
244
275
/**
248
279
                                                                           certificate_type_t cert, key_type_t key, 
249
280
                                                                           identification_t *id, bool trusted)
250
281
{
251
 
        cert_data_t *data;
 
282
        cert_enumerator_t *enumerator;
252
283
        
253
284
        if (trusted)
254
285
        {
255
286
                return NULL;
256
287
        }
257
 
        data = malloc_thing(cert_data_t);
258
 
        data->cert = cert;
259
 
        data->key = key;
260
 
        data->id = id;
261
 
        data->this = this;
 
288
        enumerator = malloc_thing(cert_enumerator_t);
 
289
        enumerator->public.enumerate = (void*)cert_enumerate;
 
290
        enumerator->public.destroy = (void*)cert_enumerator_destroy;
 
291
        enumerator->cert = cert;
 
292
        enumerator->key = key;
 
293
        enumerator->id = id;
 
294
        enumerator->relations = this->relations;
 
295
        enumerator->index = -1;
 
296
        enumerator->locked = -1;
262
297
        
263
 
        this->lock->read_lock(this->lock);
264
 
        ref_get(&this->enumerating);
265
 
        return enumerator_create_filter(
266
 
                                                        this->relations->create_enumerator(this->relations),
267
 
                                                        (void*)certs_filter, data, (void*)certs_destroy);
 
298
        return &enumerator->public;
268
299
}
269
300
 
270
301
/**
272
303
 */
273
304
static void flush(private_cert_cache_t *this, certificate_type_t type)
274
305
{
275
 
        enumerator_t *enumerator;
276
 
        relation_t *relation;
 
306
        relation_t *rel;
 
307
        int i;
277
308
        
278
 
        this->lock->write_lock(this->lock);
279
 
        enumerator = this->relations->create_enumerator(this->relations);
280
 
        while (enumerator->enumerate(enumerator, &relation))
 
309
        for (i = 0; i < CACHE_SIZE; i++)
281
310
        {
282
 
                if (type == CERT_ANY ||
283
 
                        type == relation->subject->get_type(relation->subject))
284
 
                {
285
 
                        this->relations->remove_at(this->relations, enumerator);
286
 
                        relation_destroy(relation);
287
 
                }
 
311
                rel = &this->relations[i];
 
312
                if (!rel->subject)
 
313
                {
 
314
                        continue;
 
315
                }
 
316
                /* check with cheap read lock first */
 
317
                if (type != CERT_ANY)
 
318
                {
 
319
                        rel->lock->read_lock(rel->lock);
 
320
                        if (!rel->subject || type != rel->subject->get_type(rel->subject))
 
321
                        {
 
322
                                rel->lock->unlock(rel->lock);
 
323
                                continue;
 
324
                        }
 
325
                        rel->lock->unlock(rel->lock);
 
326
                }
 
327
                /* double check in write lock */
 
328
                rel->lock->write_lock(rel->lock);
 
329
                if (rel->subject)
 
330
                {
 
331
                        if (type == CERT_ANY || type == rel->subject->get_type(rel->subject))
 
332
                        {
 
333
                                rel->subject->destroy(rel->subject);
 
334
                                rel->issuer->destroy(rel->issuer);
 
335
                                rel->subject = NULL;
 
336
                                rel->issuer = NULL;
 
337
                                rel->hits = 0;
 
338
                        }
 
339
                }
 
340
                rel->lock->unlock(rel->lock);
288
341
        }
289
 
        enumerator->destroy(enumerator);
290
 
        this->lock->unlock(this->lock);
291
342
}
292
343
 
293
344
/**
295
346
 */
296
347
static void destroy(private_cert_cache_t *this)
297
348
{
298
 
        this->relations->destroy_function(this->relations, (void*)relation_destroy);
299
 
        this->lock->destroy(this->lock);
 
349
        relation_t *rel;
 
350
        int i;
 
351
        
 
352
        for (i = 0; i < CACHE_SIZE; i++)
 
353
        {
 
354
                rel = &this->relations[i];
 
355
                if (rel->subject)
 
356
                {
 
357
                        rel->subject->destroy(rel->subject);
 
358
                        rel->issuer->destroy(rel->issuer);
 
359
                }
 
360
                rel->lock->destroy(rel->lock);
 
361
        }
300
362
        free(this);
301
363
}
302
364
 
305
367
 */
306
368
cert_cache_t *cert_cache_create()
307
369
{
308
 
        private_cert_cache_t *this = malloc_thing(private_cert_cache_t);
 
370
        private_cert_cache_t *this;
 
371
        int i;
309
372
        
 
373
        this = malloc_thing(private_cert_cache_t);
310
374
        this->public.set.create_private_enumerator = (void*)return_null;
311
375
        this->public.set.create_cert_enumerator = (void*)create_enumerator;
312
376
        this->public.set.create_shared_enumerator = (void*)return_null;
316
380
        this->public.flush = (void(*)(cert_cache_t*, certificate_type_t type))flush;
317
381
        this->public.destroy = (void(*)(cert_cache_t*))destroy;
318
382
        
319
 
        this->relations = linked_list_create();
320
 
        this->enumerating = 0;
321
 
        this->check_required = FALSE;
322
 
        this->lock = rwlock_create(RWLOCK_DEFAULT);
323
 
        
 
383
        for (i = 0; i < CACHE_SIZE; i++)
 
384
        {
 
385
                this->relations[i].subject = NULL;
 
386
                this->relations[i].issuer = NULL;
 
387
                this->relations[i].hits = 0;
 
388
                this->relations[i].lock = rwlock_create(RWLOCK_DEFAULT);
 
389
        }
324
390
        return &this->public;
325
391
}
326
392