2 * OpenSSH Multi-threaded AES-CTR Cipher
4 * Author: Benjamin Bennett <ben@psc.edu>
5 * Copyright (c) 2008 Pittsburgh Supercomputing Center. All rights reserved.
7 * Based on original OpenSSH AES-CTR cipher. Small portions remain unchanged,
8 * Copyright (c) 2003 Markus Friedl <markus@openbsd.org>
10 * Permission to use, copy, modify, and distribute this software for any
11 * purpose with or without fee is hereby granted, provided that the above
12 * copyright notice and this permission notice appear in all copies.
14 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
15 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
16 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
17 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
18 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
19 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
20 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
24 #include <sys/types.h>
29 #include <openssl/evp.h>
34 /* compatibility with old or broken OpenSSL versions */
35 #include "openbsd-compat/openssl-compat.h"
37 #ifndef USE_BUILTIN_RIJNDAEL
38 #include <openssl/aes.h>
43 /*-------------------- TUNABLES --------------------*/
44 /* Number of pregen threads to use */
45 #define CIPHER_THREADS 2
47 /* Number of keystream queues */
48 #define NUMKQ (CIPHER_THREADS + 2)
50 /* Length of a keystream queue */
53 /* Processor cacheline length */
54 #define CACHELINE_LEN 64
56 /* Collect thread stats and print at cancellation when in debug mode */
57 // #define CIPHER_THREAD_STATS
59 /* Use single-byte XOR instead of 8-byte XOR */
60 // #define CIPHER_BYTE_XOR
61 /*-------------------- END TUNABLES --------------------*/
64 const EVP_CIPHER *evp_aes_ctr_mt(void);
66 #ifdef CIPHER_THREAD_STATS
68 * Struct to collect thread stats
78 * Debug print the thread stats
79 * Use with pthread_cleanup_push for displaying at thread cancellation
82 thread_loop_stats(void *x)
84 struct thread_stats *s = x;
86 debug("tid %lu - %u fills, %u skips, %u waits", pthread_self(),
87 s->fills, s->skips, s->waits);
90 #define STATS_STRUCT(s) struct thread_stats s
91 #define STATS_INIT(s) { memset(&s, 0, sizeof(s)); }
92 #define STATS_FILL(s) { s.fills++; }
93 #define STATS_SKIP(s) { s.skips++; }
94 #define STATS_WAIT(s) { s.waits++; }
95 #define STATS_DRAIN(s) { s.drains++; }
97 #define STATS_STRUCT(s)
100 #define STATS_SKIP(s)
101 #define STATS_WAIT(s)
102 #define STATS_DRAIN(s)
105 /* Keystream Queue state */
114 /* Keystream Queue struct */
116 u_char keys[KQLEN][AES_BLOCK_SIZE];
117 u_char ctr[AES_BLOCK_SIZE];
118 u_char pad0[CACHELINE_LEN];
120 pthread_mutex_t lock;
122 u_char pad1[CACHELINE_LEN];
126 struct ssh_aes_ctr_ctx
131 u_char aes_counter[AES_BLOCK_SIZE];
132 pthread_t tid[CIPHER_THREADS];
139 * increment counter 'ctr',
140 * the counter is of size 'len' bytes and stored in network-byte-order.
141 * (LSB at ctr[len-1], MSB at ctr[0])
144 ssh_ctr_inc(u_char *ctr, u_int len)
148 for (i = len - 1; i >= 0; i--)
149 if (++ctr[i]) /* continue on overflow */
154 * Add num to counter 'ctr'
157 ssh_ctr_add(u_char *ctr, uint32_t num, u_int len)
162 for (n = 0, i = len - 1; i >= 0 && (num || n); i--) {
163 n = ctr[i] + (num & 0xff) + n;
171 * Threads may be cancelled in a pthread_cond_wait, we must free the mutex
174 thread_loop_cleanup(void *x)
176 pthread_mutex_unlock((pthread_mutex_t *)x);
180 * The life of a pregen thread:
181 * Find empty keystream queues and fill them using their counter.
182 * When done, update counter for the next fill.
189 struct ssh_aes_ctr_ctx *c = x;
194 /* Threads stats on cancellation */
196 #ifdef CIPHER_THREAD_STATS
197 pthread_cleanup_push(thread_loop_stats, &stats);
200 /* Thread local copy of AES key */
201 memcpy(&key, &c->aes_ctx, sizeof(key));
204 * Handle the special case of startup, one thread must fill
205 * the first KQ then mark it as draining. Lock held throughout.
207 if (pthread_equal(pthread_self(), c->tid[0])) {
209 pthread_mutex_lock(&q->lock);
210 if (q->qstate == KQINIT) {
211 for (i = 0; i < KQLEN; i++) {
212 AES_encrypt(q->ctr, q->keys[i], &key);
213 ssh_ctr_inc(q->ctr, AES_BLOCK_SIZE);
215 ssh_ctr_add(q->ctr, KQLEN * (NUMKQ - 1), AES_BLOCK_SIZE);
216 q->qstate = KQDRAINING;
218 pthread_cond_broadcast(&q->cond);
220 pthread_mutex_unlock(&q->lock);
226 * Normal case is to find empty queues and fill them, skipping over
227 * queues already filled by other threads and stopping to wait for
228 * a draining queue to become empty.
230 * Multiple threads may be waiting on a draining queue and awoken
231 * when empty. The first thread to wake will mark it as filling,
232 * others will move on to fill, skip, or wait on the next queue.
234 for (qidx = 1;; qidx = (qidx + 1) % NUMKQ) {
235 /* Check if I was cancelled, also checked in cond_wait */
236 pthread_testcancel();
238 /* Lock queue and block if its draining */
240 pthread_mutex_lock(&q->lock);
241 pthread_cleanup_push(thread_loop_cleanup, &q->lock);
242 while (q->qstate == KQDRAINING || q->qstate == KQINIT) {
244 pthread_cond_wait(&q->cond, &q->lock);
246 pthread_cleanup_pop(0);
248 /* If filling or full, somebody else got it, skip */
249 if (q->qstate != KQEMPTY) {
250 pthread_mutex_unlock(&q->lock);
256 * Empty, let's fill it.
257 * Queue lock is relinquished while we do this so others
258 * can see that it's being filled.
260 q->qstate = KQFILLING;
261 pthread_mutex_unlock(&q->lock);
262 for (i = 0; i < KQLEN; i++) {
263 AES_encrypt(q->ctr, q->keys[i], &key);
264 ssh_ctr_inc(q->ctr, AES_BLOCK_SIZE);
267 /* Re-lock, mark full and signal consumer */
268 pthread_mutex_lock(&q->lock);
269 ssh_ctr_add(q->ctr, KQLEN * (NUMKQ - 1), AES_BLOCK_SIZE);
272 pthread_cond_signal(&q->cond);
273 pthread_mutex_unlock(&q->lock);
276 #ifdef CIPHER_THREAD_STATS
278 pthread_cleanup_pop(1);
285 ssh_aes_ctr(EVP_CIPHER_CTX *ctx, u_char *dest, const u_char *src,
288 struct ssh_aes_ctr_ctx *c;
295 if ((c = EVP_CIPHER_CTX_get_app_data(ctx)) == NULL)
301 /* src already padded to block multiple */
305 #ifdef CIPHER_BYTE_XOR
306 dest[0] = src[0] ^ buf[0];
307 dest[1] = src[1] ^ buf[1];
308 dest[2] = src[2] ^ buf[2];
309 dest[3] = src[3] ^ buf[3];
310 dest[4] = src[4] ^ buf[4];
311 dest[5] = src[5] ^ buf[5];
312 dest[6] = src[6] ^ buf[6];
313 dest[7] = src[7] ^ buf[7];
314 dest[8] = src[8] ^ buf[8];
315 dest[9] = src[9] ^ buf[9];
316 dest[10] = src[10] ^ buf[10];
317 dest[11] = src[11] ^ buf[11];
318 dest[12] = src[12] ^ buf[12];
319 dest[13] = src[13] ^ buf[13];
320 dest[14] = src[14] ^ buf[14];
321 dest[15] = src[15] ^ buf[15];
323 *(uint64_t *)dest = *(uint64_t *)src ^ *(uint64_t *)buf;
324 *(uint64_t *)(dest + 8) = *(uint64_t *)(src + 8) ^
325 *(uint64_t *)(buf + 8);
331 ssh_ctr_inc(ctx->iv, AES_BLOCK_SIZE);
333 /* Increment read index, switch queues on rollover */
334 if ((ridx = (ridx + 1) % KQLEN) == 0) {
337 /* Mark next queue draining, may need to wait */
338 c->qidx = (c->qidx + 1) % NUMKQ;
340 pthread_mutex_lock(&q->lock);
341 while (q->qstate != KQFULL) {
342 STATS_WAIT(c->stats);
343 pthread_cond_wait(&q->cond, &q->lock);
345 q->qstate = KQDRAINING;
346 pthread_mutex_unlock(&q->lock);
348 /* Mark consumed queue empty and signal producers */
349 pthread_mutex_lock(&oldq->lock);
350 oldq->qstate = KQEMPTY;
351 STATS_DRAIN(c->stats);
352 pthread_cond_broadcast(&oldq->cond);
353 pthread_mutex_unlock(&oldq->lock);
364 ssh_aes_ctr_init(EVP_CIPHER_CTX *ctx, const u_char *key, const u_char *iv,
367 struct ssh_aes_ctr_ctx *c;
370 if ((c = EVP_CIPHER_CTX_get_app_data(ctx)) == NULL) {
371 c = xmalloc(sizeof(*c));
373 c->state = HAVE_NONE;
374 for (i = 0; i < NUMKQ; i++) {
375 pthread_mutex_init(&c->q[i].lock, NULL);
376 pthread_cond_init(&c->q[i].cond, NULL);
379 STATS_INIT(c->stats);
381 EVP_CIPHER_CTX_set_app_data(ctx, c);
384 if (c->state == (HAVE_KEY | HAVE_IV)) {
385 /* Cancel pregen threads */
386 for (i = 0; i < CIPHER_THREADS; i++)
387 pthread_cancel(c->tid[i]);
388 for (i = 0; i < CIPHER_THREADS; i++)
389 pthread_join(c->tid[i], NULL);
390 /* Start over getting key & iv */
391 c->state = HAVE_NONE;
395 AES_set_encrypt_key(key, EVP_CIPHER_CTX_key_length(ctx) * 8,
397 c->state |= HAVE_KEY;
401 memcpy(ctx->iv, iv, AES_BLOCK_SIZE);
405 if (c->state == (HAVE_KEY | HAVE_IV)) {
407 memcpy(c->q[0].ctr, ctx->iv, AES_BLOCK_SIZE);
408 c->q[0].qstate = KQINIT;
409 for (i = 1; i < NUMKQ; i++) {
410 memcpy(c->q[i].ctr, ctx->iv, AES_BLOCK_SIZE);
411 ssh_ctr_add(c->q[i].ctr, i * KQLEN, AES_BLOCK_SIZE);
412 c->q[i].qstate = KQEMPTY;
418 for (i = 0; i < CIPHER_THREADS; i++) {
419 pthread_create(&c->tid[i], NULL, thread_loop, c);
421 pthread_mutex_lock(&c->q[0].lock);
422 while (c->q[0].qstate != KQDRAINING)
423 pthread_cond_wait(&c->q[0].cond, &c->q[0].lock);
424 pthread_mutex_unlock(&c->q[0].lock);
431 ssh_aes_ctr_cleanup(EVP_CIPHER_CTX *ctx)
433 struct ssh_aes_ctr_ctx *c;
436 if ((c = EVP_CIPHER_CTX_get_app_data(ctx)) != NULL) {
437 #ifdef CIPHER_THREAD_STATS
438 debug("main thread: %u drains, %u waits", c->stats.drains,
441 /* Cancel pregen threads */
442 for (i = 0; i < CIPHER_THREADS; i++)
443 pthread_cancel(c->tid[i]);
444 for (i = 0; i < CIPHER_THREADS; i++)
445 pthread_join(c->tid[i], NULL);
447 memset(c, 0, sizeof(*c));
449 EVP_CIPHER_CTX_set_app_data(ctx, NULL);
458 static EVP_CIPHER aes_ctr;
460 memset(&aes_ctr, 0, sizeof(EVP_CIPHER));
461 aes_ctr.nid = NID_undef;
462 aes_ctr.block_size = AES_BLOCK_SIZE;
463 aes_ctr.iv_len = AES_BLOCK_SIZE;
464 aes_ctr.key_len = 16;
465 aes_ctr.init = ssh_aes_ctr_init;
466 aes_ctr.cleanup = ssh_aes_ctr_cleanup;
467 aes_ctr.do_cipher = ssh_aes_ctr;
469 aes_ctr.flags = EVP_CIPH_CBC_MODE | EVP_CIPH_VARIABLE_LENGTH |
470 EVP_CIPH_ALWAYS_CALL_INIT | EVP_CIPH_CUSTOM_IV;