Guest User

Untitled

a guest
Sep 10th, 2013
19,904
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // This is a quick analysis of Linux's use of RDRAND. All double-slash (//)
  2. // style comments are my own, all slash-star (/*) style comments are from the
  3. // original code. This was written by Taylor Hornby (@DefuseSec).
  4.  
  5. // This is part of the drivers/char/random.c file.
  6. // I have re-ordered the procedures for clarity. Everything inside them (except
  7. // comments) is exactly as you will find it in linux-3.11.tar.xz
  8.  
  9. // This comment says it 'does not use' the hardware RNG. It actually does.
  10. /*
  11.  * This function is the exported kernel interface.  It returns some
  12.  * number of good random numbers, suitable for key generation, seeding
  13.  * TCP sequence numbers, etc.  It does not use the hw random number
  14.  * generator, if available; use get_random_bytes_arch() for that.
  15.  */
  16. void get_random_bytes(void *buf, int nbytes)
  17. {
  18.     extract_entropy(&nonblocking_pool, buf, nbytes, 0, 0);
  19. }
  20. EXPORT_SYMBOL(get_random_bytes);
  21.  
  22.  
  23. // This one is called by get_random_bytes above.
  24. static ssize_t extract_entropy(struct entropy_store *r, void *buf,
  25.                  size_t nbytes, int min, int reserved)
  26. {
  27.     ssize_t ret = 0, i;
  28.     __u8 tmp[EXTRACT_SIZE];
  29.     unsigned long flags;
  30.  
  31.     /* if last_data isn't primed, we need EXTRACT_SIZE extra bytes */
  32.     if (fips_enabled) {
  33.         spin_lock_irqsave(&r->lock, flags);
  34.         if (!r->last_data_init) {
  35.             r->last_data_init = true;
  36.             spin_unlock_irqrestore(&r->lock, flags);
  37.             trace_extract_entropy(r->name, EXTRACT_SIZE,
  38.                           r->entropy_count, _RET_IP_);
  39.             xfer_secondary_pool(r, EXTRACT_SIZE);
  40.             extract_buf(r, tmp);
  41.             spin_lock_irqsave(&r->lock, flags);
  42.             memcpy(r->last_data, tmp, EXTRACT_SIZE);
  43.         }
  44.         spin_unlock_irqrestore(&r->lock, flags);
  45.     }
  46.  
  47.     trace_extract_entropy(r->name, nbytes, r->entropy_count, _RET_IP_);
  48.     xfer_secondary_pool(r, nbytes);
  49.     nbytes = account(r, nbytes, min, reserved);
  50.  
  51.     while (nbytes) {
  52.         // Each iteration of this loop:
  53.         // - Extracts 'EXTRACT_SIZE' bytes from extract_buf
  54.         // - Panic if the just-extracted bytes are the same as the
  55.         //   previously-extracted bytes.
  56.         // - Copy either EXTRACT_SIZE or nbytes into the output.
  57.         extract_buf(r, tmp);
  58.  
  59.         if (fips_enabled) {
  60.             spin_lock_irqsave(&r->lock, flags);
  61.             if (!memcmp(tmp, r->last_data, EXTRACT_SIZE))
  62.                 panic("Hardware RNG duplicated output!\n");
  63.             memcpy(r->last_data, tmp, EXTRACT_SIZE);
  64.             spin_unlock_irqrestore(&r->lock, flags);
  65.         }
  66.         i = min_t(int, nbytes, EXTRACT_SIZE);
  67.         memcpy(buf, tmp, i);
  68.         nbytes -= i;
  69.         buf += i;
  70.         ret += i;
  71.     }
  72.  
  73.     /* Wipe data just returned from memory */
  74.     memset(tmp, 0, sizeof(tmp));
  75.  
  76.     return ret;
  77. }
  78.  
  79. // This fills 'out' with EXTRACT_BYTES random bytes. It's what extract_entropy
  80. // uses to fill its output buffer.
  81. static void extract_buf(struct entropy_store *r, __u8 *out)
  82. {
  83.     // Skip all this stuff because it doesn't matter for the point I want to
  84.     // make...
  85.     int i;
  86.     union {
  87.         __u32 w[5];
  88.         unsigned long l[LONGS(EXTRACT_SIZE)];
  89.     } hash;
  90.     __u32 workspace[SHA_WORKSPACE_WORDS];
  91.     __u8 extract[64];
  92.     unsigned long flags;
  93.  
  94.     /* Generate a hash across the pool, 16 words (512 bits) at a time */
  95.     sha_init(hash.w);
  96.     spin_lock_irqsave(&r->lock, flags);
  97.     for (i = 0; i < r->poolinfo->poolwords; i += 16)
  98.         sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
  99.  
  100.     /*
  101.      * We mix the hash back into the pool to prevent backtracking
  102.      * attacks (where the attacker knows the state of the pool
  103.      * plus the current outputs, and attempts to find previous
  104.      * ouputs), unless the hash function can be inverted. By
  105.      * mixing at least a SHA1 worth of hash data back, we make
  106.      * brute-forcing the feedback as hard as brute-forcing the
  107.      * hash.
  108.      */
  109.     __mix_pool_bytes(r, hash.w, sizeof(hash.w), extract);
  110.     spin_unlock_irqrestore(&r->lock, flags);
  111.  
  112.     /*
  113.      * To avoid duplicates, we atomically extract a portion of the
  114.      * pool while mixing, and hash one final time.
  115.      */
  116.     sha_transform(hash.w, extract, workspace);
  117.     memset(extract, 0, sizeof(extract));
  118.     memset(workspace, 0, sizeof(workspace));
  119.  
  120.     /*
  121.      * In case the hash function has some recognizable output
  122.      * pattern, we fold it in half. Thus, we always feed back
  123.      * twice as much data as we output.
  124.      */
  125.     hash.w[0] ^= hash.w[3];
  126.     hash.w[1] ^= hash.w[4];
  127.     hash.w[2] ^= rol32(hash.w[2], 16);
  128.  
  129.     // Ah, here we are. Finally, we found RDRAND.
  130.     // This XOR's RDRAND *directly* into the output buffer, right before
  131.     // returning.
  132.     /*
  133.      * If we have a architectural hardware random number
  134.      * generator, mix that in, too.
  135.      */
  136.     for (i = 0; i < LONGS(EXTRACT_SIZE); i++) {
  137.         unsigned long v;
  138.         // arch_get_random is RDRAND.
  139.         if (!arch_get_random_long(&v))
  140.             break;
  141.         hash.l[i] ^= v;
  142.     }
  143.     // SIMPLICIO: Why is that a problem? I thought if you XOR a non-random
  144.     //            stream with a random one, you get a random one? Remember,
  145.     //            one-time-pads and such?
  146.     //
  147.     // SALVIATI:  Right, that's true. Even if RDRAND returns all zeroes, or some
  148.     //            completely predictable sequence, the output will be random as
  149.     //            long as it was random before the XOR.
  150.     //
  151.     // SIMPLICIO: So what's the problem, then? It seems like having RDRAND here
  152.     //            can only make things better...
  153.     //
  154.     // SALVIATI:  Ah, that's true if RDRAND might only be a weak source of
  155.     //            entropy, but if it's *actively* malicious, it could seriously
  156.     //            compromise the security of the output. For example, it could
  157.     //            purposely return the inverse of the bits it's going to be
  158.     //            XORed with, resulting in this function filling 'out' with zero
  159.     //            bytes.
  160.     //
  161.     // SIMPLICIO: That's rediculous! How could RDRAND know which bits it's going
  162.     //            to be XORed with? There's no way one instruction could figure
  163.     //            all of that out.
  164.     //
  165.     // SALVIATI:  Actually, it's quite possible. The procesor wouldn't even have
  166.     //            to be smart about it. Chances are, the bits it's going to be
  167.     //            XORed with are in cache (which is inside the CPU), so if the
  168.     //            CPU had RDRAND return the XOR of all longs in the cache, it
  169.     //            would cancel out and information about the state of the cache
  170.     //            would leak out through the RNG. There are plenty of other
  171.     //            ways. This is the CPU, remember. It can pretty much do
  172.     //            anything it wants.
  173.     //
  174.     // SIMPLICIO: Ok, I see how this use of RDRAND could *in theory* weaken the
  175.     //            whole RNG. But wouldn't that be pretty easy to detect, and
  176.     //            can't we trust Intel? If the NSA has their hand up Intel's
  177.     //            ass, wouldn't there be easier ways of backdooring a system?
  178.     //
  179.     // SALVIATI:  The RDRAND backdoor could be made so that it only activates
  180.     //            under certain, very specific, conditions. For example, it
  181.     //            might only activate when RAX contains 0x632472F72B3FB507,
  182.     //            which is extremely unlikely to happen during normal use, but
  183.     //            could be made to happen by sending the system a TCP packet,
  184.     //            web page, etc, containing that value. So, if it existed, it
  185.     //            would be extremely difficult to detect. It's possible in
  186.     //            principal to reverse engineer the CPU itself, but it's
  187.     //            extremely expensive -- and destructive -- so you can't check
  188.     //            all of the CPUs you actually use for backdoors. Sure, if the
  189.     //            NSA controlled Intel, there would be easier ways to backdoor
  190.     //            a system, but backdooring the RNG is nice, because it's
  191.     //            passive: You don't have to *do* anything to a system in order
  192.     //            to break it. You can just listen to the system's network
  193.     //            traffic and use your RNG backdoor to decrypt it. Futher, it's
  194.     //            bad design to combine two RNGs by XORing them together. They
  195.     //            may be correlated (by accident or on purpose) in subtle ways
  196.     //            that cancel out security. To be honest, I'm not exactly sure
  197.     //            what the best way would be, but it certainly isn't XOR.
  198.     //
  199.  
  200.     memcpy(out, &hash, EXTRACT_SIZE);
  201.     memset(&hash, 0, sizeof(hash));
  202. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×