Neil Horman | b8454ee | 2008-07-07 22:41:31 +0800 | [diff] [blame] | 1 | /* |
| 2 | * PRNG: Pseudo Random Number Generator |
| 3 | * Based on NIST Recommended PRNG From ANSI X9.31 Appendix A.2.4 using |
| 4 | * AES 128 cipher in RFC3686 ctr mode |
| 5 | * |
| 6 | * (C) Neil Horman <nhorman@tuxdriver.com> |
| 7 | * |
| 8 | * This program is free software; you can redistribute it and/or modify it |
| 9 | * under the terms of the GNU General Public License as published by the |
| 10 | * Free Software Foundation; either version 2 of the License, or (at your |
| 11 | * any later version. |
| 12 | * |
| 13 | * |
| 14 | */ |
| 15 | |
| 16 | #include <linux/err.h> |
| 17 | #include <linux/init.h> |
| 18 | #include <linux/module.h> |
| 19 | #include <linux/mm.h> |
| 20 | #include <linux/slab.h> |
| 21 | #include <linux/fs.h> |
| 22 | #include <linux/scatterlist.h> |
| 23 | #include <linux/string.h> |
| 24 | #include <linux/crypto.h> |
| 25 | #include <linux/highmem.h> |
| 26 | #include <linux/moduleparam.h> |
| 27 | #include <linux/jiffies.h> |
| 28 | #include <linux/timex.h> |
| 29 | #include <linux/interrupt.h> |
| 30 | #include <linux/miscdevice.h> |
| 31 | #include "prng.h" |
| 32 | |
| 33 | #define TEST_PRNG_ON_START 0 |
| 34 | |
| 35 | #define DEFAULT_PRNG_KEY "0123456789abcdef1011" |
| 36 | #define DEFAULT_PRNG_KSZ 20 |
| 37 | #define DEFAULT_PRNG_IV "defaultv" |
| 38 | #define DEFAULT_PRNG_IVSZ 8 |
| 39 | #define DEFAULT_BLK_SZ 16 |
| 40 | #define DEFAULT_V_SEED "zaybxcwdveuftgsh" |
| 41 | |
| 42 | /* |
| 43 | * Flags for the prng_context flags field |
| 44 | */ |
| 45 | |
| 46 | #define PRNG_FIXED_SIZE 0x1 |
| 47 | #define PRNG_NEED_RESET 0x2 |
| 48 | |
| 49 | /* |
| 50 | * Note: DT is our counter value |
| 51 | * I is our intermediate value |
| 52 | * V is our seed vector |
| 53 | * See http://csrc.nist.gov/groups/STM/cavp/documents/rng/931rngext.pdf |
| 54 | * for implementation details |
| 55 | */ |
| 56 | |
| 57 | |
| 58 | struct prng_context { |
| 59 | char *prng_key; |
| 60 | char *prng_iv; |
| 61 | spinlock_t prng_lock; |
| 62 | unsigned char rand_data[DEFAULT_BLK_SZ]; |
| 63 | unsigned char last_rand_data[DEFAULT_BLK_SZ]; |
| 64 | unsigned char DT[DEFAULT_BLK_SZ]; |
| 65 | unsigned char I[DEFAULT_BLK_SZ]; |
| 66 | unsigned char V[DEFAULT_BLK_SZ]; |
| 67 | u32 rand_data_valid; |
| 68 | struct crypto_blkcipher *tfm; |
| 69 | u32 flags; |
| 70 | }; |
| 71 | |
| 72 | static int dbg; |
| 73 | |
| 74 | static void hexdump(char *note, unsigned char *buf, unsigned int len) |
| 75 | { |
| 76 | if (dbg) { |
| 77 | printk(KERN_CRIT "%s", note); |
| 78 | print_hex_dump(KERN_CONT, "", DUMP_PREFIX_OFFSET, |
| 79 | 16, 1, |
| 80 | buf, len, false); |
| 81 | } |
| 82 | } |
| 83 | |
| 84 | #define dbgprint(format, args...) do {if(dbg) printk(format, ##args);} while(0) |
| 85 | |
| 86 | static void xor_vectors(unsigned char *in1, unsigned char *in2, |
| 87 | unsigned char *out, unsigned int size) |
| 88 | { |
| 89 | int i; |
| 90 | |
| 91 | for (i=0;i<size;i++) |
| 92 | out[i] = in1[i] ^ in2[i]; |
| 93 | |
| 94 | } |
| 95 | /* |
| 96 | * Returns DEFAULT_BLK_SZ bytes of random data per call |
| 97 | * returns 0 if generation succeded, <0 if something went wrong |
| 98 | */ |
| 99 | static int _get_more_prng_bytes(struct prng_context *ctx) |
| 100 | { |
| 101 | int i; |
| 102 | struct blkcipher_desc desc; |
| 103 | struct scatterlist sg_in, sg_out; |
| 104 | int ret; |
| 105 | unsigned char tmp[DEFAULT_BLK_SZ]; |
| 106 | |
| 107 | desc.tfm = ctx->tfm; |
| 108 | desc.flags = 0; |
| 109 | |
| 110 | |
| 111 | dbgprint(KERN_CRIT "Calling _get_more_prng_bytes for context %p\n",ctx); |
| 112 | |
| 113 | hexdump("Input DT: ", ctx->DT, DEFAULT_BLK_SZ); |
| 114 | hexdump("Input I: ", ctx->I, DEFAULT_BLK_SZ); |
| 115 | hexdump("Input V: ", ctx->V, DEFAULT_BLK_SZ); |
| 116 | |
| 117 | /* |
| 118 | * This algorithm is a 3 stage state machine |
| 119 | */ |
| 120 | for (i=0;i<3;i++) { |
| 121 | |
| 122 | desc.tfm = ctx->tfm; |
| 123 | desc.flags = 0; |
| 124 | switch (i) { |
| 125 | case 0: |
| 126 | /* |
| 127 | * Start by encrypting the counter value |
| 128 | * This gives us an intermediate value I |
| 129 | */ |
| 130 | memcpy(tmp, ctx->DT, DEFAULT_BLK_SZ); |
| 131 | sg_init_one(&sg_out, &ctx->I[0], DEFAULT_BLK_SZ); |
| 132 | hexdump("tmp stage 0: ", tmp, DEFAULT_BLK_SZ); |
| 133 | break; |
| 134 | case 1: |
| 135 | |
| 136 | /* |
| 137 | * Next xor I with our secret vector V |
| 138 | * encrypt that result to obtain our |
| 139 | * pseudo random data which we output |
| 140 | */ |
| 141 | xor_vectors(ctx->I, ctx->V, tmp, DEFAULT_BLK_SZ); |
| 142 | sg_init_one(&sg_out, &ctx->rand_data[0], DEFAULT_BLK_SZ); |
| 143 | hexdump("tmp stage 1: ", tmp, DEFAULT_BLK_SZ); |
| 144 | break; |
| 145 | case 2: |
| 146 | /* |
| 147 | * First check that we didn't produce the same random data |
| 148 | * that we did last time around through this |
| 149 | */ |
| 150 | if (!memcmp(ctx->rand_data, ctx->last_rand_data, DEFAULT_BLK_SZ)) { |
| 151 | printk(KERN_ERR "ctx %p Failed repetition check!\n", |
| 152 | ctx); |
| 153 | ctx->flags |= PRNG_NEED_RESET; |
| 154 | return -1; |
| 155 | } |
| 156 | memcpy(ctx->last_rand_data, ctx->rand_data, DEFAULT_BLK_SZ); |
| 157 | |
| 158 | /* |
| 159 | * Lastly xor the random data with I |
| 160 | * and encrypt that to obtain a new secret vector V |
| 161 | */ |
| 162 | xor_vectors(ctx->rand_data, ctx->I, tmp, DEFAULT_BLK_SZ); |
| 163 | sg_init_one(&sg_out, &ctx->V[0], DEFAULT_BLK_SZ); |
| 164 | hexdump("tmp stage 2: ", tmp, DEFAULT_BLK_SZ); |
| 165 | break; |
| 166 | } |
| 167 | |
| 168 | /* Initialize our input buffer */ |
| 169 | sg_init_one(&sg_in, &tmp[0], DEFAULT_BLK_SZ); |
| 170 | |
| 171 | /* do the encryption */ |
| 172 | ret = crypto_blkcipher_encrypt(&desc, &sg_out, &sg_in, DEFAULT_BLK_SZ); |
| 173 | |
| 174 | /* And check the result */ |
| 175 | if (ret) { |
| 176 | dbgprint(KERN_CRIT "Encryption of new block failed for context %p\n",ctx); |
| 177 | ctx->rand_data_valid = DEFAULT_BLK_SZ; |
| 178 | return -1; |
| 179 | } |
| 180 | |
| 181 | } |
| 182 | |
| 183 | /* |
| 184 | * Now update our DT value |
| 185 | */ |
| 186 | for (i=DEFAULT_BLK_SZ-1;i>0;i--) { |
| 187 | ctx->DT[i] = ctx->DT[i-1]; |
| 188 | } |
| 189 | ctx->DT[0] += 1; |
| 190 | |
| 191 | dbgprint("Returning new block for context %p\n",ctx); |
| 192 | ctx->rand_data_valid = 0; |
| 193 | |
| 194 | hexdump("Output DT: ", ctx->DT, DEFAULT_BLK_SZ); |
| 195 | hexdump("Output I: ", ctx->I, DEFAULT_BLK_SZ); |
| 196 | hexdump("Output V: ", ctx->V, DEFAULT_BLK_SZ); |
| 197 | hexdump("New Random Data: ", ctx->rand_data, DEFAULT_BLK_SZ); |
| 198 | |
| 199 | return 0; |
| 200 | } |
| 201 | |
| 202 | /* Our exported functions */ |
| 203 | int get_prng_bytes(char *buf, int nbytes, struct prng_context *ctx) |
| 204 | { |
| 205 | unsigned long flags; |
| 206 | unsigned char *ptr = buf; |
| 207 | unsigned int byte_count = (unsigned int)nbytes; |
| 208 | int err; |
| 209 | |
| 210 | |
| 211 | if (nbytes < 0) |
| 212 | return -EINVAL; |
| 213 | |
| 214 | spin_lock_irqsave(&ctx->prng_lock, flags); |
| 215 | |
| 216 | err = -EFAULT; |
| 217 | if (ctx->flags & PRNG_NEED_RESET) |
| 218 | goto done; |
| 219 | |
| 220 | /* |
| 221 | * If the FIXED_SIZE flag is on, only return whole blocks of |
| 222 | * pseudo random data |
| 223 | */ |
| 224 | err = -EINVAL; |
| 225 | if (ctx->flags & PRNG_FIXED_SIZE) { |
| 226 | if (nbytes < DEFAULT_BLK_SZ) |
| 227 | goto done; |
| 228 | byte_count = DEFAULT_BLK_SZ; |
| 229 | } |
| 230 | |
| 231 | err = byte_count; |
| 232 | |
| 233 | dbgprint(KERN_CRIT "getting %d random bytes for context %p\n",byte_count, ctx); |
| 234 | |
| 235 | |
| 236 | remainder: |
| 237 | if (ctx->rand_data_valid == DEFAULT_BLK_SZ) { |
| 238 | if (_get_more_prng_bytes(ctx) < 0) { |
| 239 | memset(buf, 0, nbytes); |
| 240 | err = -EFAULT; |
| 241 | goto done; |
| 242 | } |
| 243 | } |
| 244 | |
| 245 | /* |
| 246 | * Copy up to the next whole block size |
| 247 | */ |
| 248 | if (byte_count < DEFAULT_BLK_SZ) { |
| 249 | for (;ctx->rand_data_valid < DEFAULT_BLK_SZ; ctx->rand_data_valid++) { |
| 250 | *ptr = ctx->rand_data[ctx->rand_data_valid]; |
| 251 | ptr++; |
| 252 | byte_count--; |
| 253 | if (byte_count == 0) |
| 254 | goto done; |
| 255 | } |
| 256 | } |
| 257 | |
| 258 | /* |
| 259 | * Now copy whole blocks |
| 260 | */ |
| 261 | for(;byte_count >= DEFAULT_BLK_SZ; byte_count -= DEFAULT_BLK_SZ) { |
| 262 | if (_get_more_prng_bytes(ctx) < 0) { |
| 263 | memset(buf, 0, nbytes); |
| 264 | err = -1; |
| 265 | goto done; |
| 266 | } |
| 267 | memcpy(ptr, ctx->rand_data, DEFAULT_BLK_SZ); |
| 268 | ctx->rand_data_valid += DEFAULT_BLK_SZ; |
| 269 | ptr += DEFAULT_BLK_SZ; |
| 270 | } |
| 271 | |
| 272 | /* |
| 273 | * Now copy any extra partial data |
| 274 | */ |
| 275 | if (byte_count) |
| 276 | goto remainder; |
| 277 | |
| 278 | done: |
| 279 | spin_unlock_irqrestore(&ctx->prng_lock, flags); |
| 280 | dbgprint(KERN_CRIT "returning %d from get_prng_bytes in context %p\n",err, ctx); |
| 281 | return err; |
| 282 | } |
| 283 | EXPORT_SYMBOL_GPL(get_prng_bytes); |
| 284 | |
| 285 | struct prng_context *alloc_prng_context(void) |
| 286 | { |
| 287 | struct prng_context *ctx=kzalloc(sizeof(struct prng_context), GFP_KERNEL); |
| 288 | |
| 289 | spin_lock_init(&ctx->prng_lock); |
| 290 | |
| 291 | if (reset_prng_context(ctx, NULL, NULL, NULL, NULL)) { |
| 292 | kfree(ctx); |
| 293 | ctx = NULL; |
| 294 | } |
| 295 | |
| 296 | dbgprint(KERN_CRIT "returning context %p\n",ctx); |
| 297 | return ctx; |
| 298 | } |
| 299 | |
| 300 | EXPORT_SYMBOL_GPL(alloc_prng_context); |
| 301 | |
| 302 | void free_prng_context(struct prng_context *ctx) |
| 303 | { |
| 304 | crypto_free_blkcipher(ctx->tfm); |
| 305 | kfree(ctx); |
| 306 | } |
| 307 | EXPORT_SYMBOL_GPL(free_prng_context); |
| 308 | |
| 309 | int reset_prng_context(struct prng_context *ctx, |
| 310 | unsigned char *key, unsigned char *iv, |
| 311 | unsigned char *V, unsigned char *DT) |
| 312 | { |
| 313 | int ret; |
| 314 | int iv_len; |
| 315 | int rc = -EFAULT; |
| 316 | |
| 317 | spin_lock(&ctx->prng_lock); |
| 318 | ctx->flags |= PRNG_NEED_RESET; |
| 319 | |
| 320 | if (key) |
| 321 | memcpy(ctx->prng_key,key,strlen(ctx->prng_key)); |
| 322 | else |
| 323 | ctx->prng_key = DEFAULT_PRNG_KEY; |
| 324 | |
| 325 | if (iv) |
| 326 | memcpy(ctx->prng_iv,iv, strlen(ctx->prng_iv)); |
| 327 | else |
| 328 | ctx->prng_iv = DEFAULT_PRNG_IV; |
| 329 | |
| 330 | if (V) |
| 331 | memcpy(ctx->V,V,DEFAULT_BLK_SZ); |
| 332 | else |
| 333 | memcpy(ctx->V,DEFAULT_V_SEED,DEFAULT_BLK_SZ); |
| 334 | |
| 335 | if (DT) |
| 336 | memcpy(ctx->DT, DT, DEFAULT_BLK_SZ); |
| 337 | else |
| 338 | memset(ctx->DT, 0, DEFAULT_BLK_SZ); |
| 339 | |
| 340 | memset(ctx->rand_data,0,DEFAULT_BLK_SZ); |
| 341 | memset(ctx->last_rand_data,0,DEFAULT_BLK_SZ); |
| 342 | |
| 343 | if (ctx->tfm) |
| 344 | crypto_free_blkcipher(ctx->tfm); |
| 345 | |
| 346 | ctx->tfm = crypto_alloc_blkcipher("rfc3686(ctr(aes))",0,0); |
| 347 | if (!ctx->tfm) { |
| 348 | dbgprint(KERN_CRIT "Failed to alloc crypto tfm for context %p\n",ctx->tfm); |
| 349 | goto out; |
| 350 | } |
| 351 | |
| 352 | ctx->rand_data_valid = DEFAULT_BLK_SZ; |
| 353 | |
| 354 | ret = crypto_blkcipher_setkey(ctx->tfm, ctx->prng_key, strlen(ctx->prng_key)); |
| 355 | if (ret) { |
| 356 | dbgprint(KERN_CRIT "PRNG: setkey() failed flags=%x\n", |
| 357 | crypto_blkcipher_get_flags(ctx->tfm)); |
| 358 | crypto_free_blkcipher(ctx->tfm); |
| 359 | goto out; |
| 360 | } |
| 361 | |
| 362 | iv_len = crypto_blkcipher_ivsize(ctx->tfm); |
| 363 | if (iv_len) { |
| 364 | crypto_blkcipher_set_iv(ctx->tfm, ctx->prng_iv, iv_len); |
| 365 | } |
| 366 | rc = 0; |
| 367 | ctx->flags &= ~PRNG_NEED_RESET; |
| 368 | out: |
| 369 | spin_unlock(&ctx->prng_lock); |
| 370 | |
| 371 | return rc; |
| 372 | |
| 373 | } |
| 374 | EXPORT_SYMBOL_GPL(reset_prng_context); |
| 375 | |
| 376 | /* Module initalization */ |
| 377 | static int __init prng_mod_init(void) |
| 378 | { |
| 379 | |
| 380 | #ifdef TEST_PRNG_ON_START |
| 381 | int i; |
| 382 | unsigned char tmpbuf[DEFAULT_BLK_SZ]; |
| 383 | |
| 384 | struct prng_context *ctx = alloc_prng_context(); |
| 385 | if (ctx == NULL) |
| 386 | return -EFAULT; |
| 387 | for (i=0;i<16;i++) { |
| 388 | if (get_prng_bytes(tmpbuf, DEFAULT_BLK_SZ, ctx) < 0) { |
| 389 | free_prng_context(ctx); |
| 390 | return -EFAULT; |
| 391 | } |
| 392 | } |
| 393 | free_prng_context(ctx); |
| 394 | #endif |
| 395 | |
| 396 | return 0; |
| 397 | } |
| 398 | |
| 399 | static void __exit prng_mod_fini(void) |
| 400 | { |
| 401 | return; |
| 402 | } |
| 403 | |
| 404 | MODULE_LICENSE("GPL"); |
| 405 | MODULE_DESCRIPTION("Software Pseudo Random Number Generator"); |
| 406 | MODULE_AUTHOR("Neil Horman <nhorman@tuxdriver.com>"); |
| 407 | module_param(dbg, int, 0); |
| 408 | MODULE_PARM_DESC(dbg, "Boolean to enable debugging (0/1 == off/on)"); |
| 409 | module_init(prng_mod_init); |
| 410 | module_exit(prng_mod_fini); |