This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Sep 10th, 2013  |  syntax: C  |  size: 8.26 KB  |  views: 15,571  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }
clone this paste RAW Paste Data