Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

For a project using RC4, the output is to be mapped to values of 0 to 35. Thus, only 36 unique output values representing the letters A to Z and 0 to 9.

To avoid bias, the RC4 byte output (with a range of 0 to 255) is discarded if the value is greater than 251. The output is then mod 36, which then maps the output into the range of 0 to 35.

Does this effectively reduce the strength of RC4 by taking this mapping step, or does the security remain unchanged? How does one measure the amount of decrease in the security? Does it relate to the loss of the values 252, 253, 254 and 255? Or, would it also be a factor of doing the mod 36 step because of reducing the possible output values to 1/7th of the original.

Thanks!

share|improve this question
    
For what are you using these numbers? –  Paŭlo Ebermann Nov 3 '11 at 22:15
    
Micro-controller application (so limited capabilities). It is to encrypt a text stream which consists of A-Z and 0-9. The plain will be added mod 36 to the adjusted RC4 output. The result will be output as the cipher text. –  Deskguy Nov 3 '11 at 22:18

2 Answers 2

On the first glance, this base 36 key stream looks at least as secure as RC4 itself - you are simply discarding some of the output, and not introducing any bias.

Note that there are some general weaknesses with in the start of the output of RC4, which means that it is normally recommended to discard the first 1000 or so bytes after initialization (I have to look the details up, but right I'm on a quite slow computer). And of course, never reuse one key for more than one message stream.

Also, the discarded bytes might be traceable with a side-channel attack (timing and/or power traces), if your micro-controller lives in a hostile environment.

share|improve this answer
1  
Agreed about the initial discard. As noted on the Wikipedia article about RC4-drop, I'm tossing the first 3072 outputs. –  Deskguy Nov 4 '11 at 0:20
    
I was careful to not introduce any new bias, but is it apparent that by working with only 36 possible outputs, rather than the full 256, that I would be reducing the security level? I can't quite wrap my mind around that part. –  Deskguy Nov 4 '11 at 0:23
1  
The "security level" here mainly depends on the key size, which does not change by changing the output. (And you should also additionally apply a MAC, since the ciphertext is malleable - changing the ciphertext allows changing the corresponding plaintext in predictable ways.) –  Paŭlo Ebermann Nov 4 '11 at 0:42

By discarding values 252 to 255, you effectively avoid introducing any new bias; the generic method is expressed in many places, e.g. this article (page 3). To generate random values between $0$ and $d-1$ (inclusive) from a PRNG which produces bit, you do the following:

  1. Choose an integer $r$ such that $2^r \geq d$.
  2. Obtain a $r$-bit word $x$ from the PRNG.
  3. Compute $t = \lfloor \frac{x}{d} \rfloor$.
  4. If $d+td \gt 2^r$, go back to step 2.
  5. Output $x - td$.

Your proposal is equivalent to the algorithm above with $d = 36$ and $r = 8$ (you work with 8-bit words, colloquially known as "bytes").

There are trade-offs about the choice of $r$, which depend on what the hardware and software can do. On an 8-bit CPU with very little power, using bytes is certainly efficient, but involves either doing a division (which will be expensive in CPU time) or using a lookup table with 256 entries (so 256 bytes of ROM -- probably tolerable, since RC4 itself requires 256 bytes of RAM, and RAM is much more expensive than ROM). Speaking of which, RC4 is not necessarily the best choice, performance wise: there are other stream ciphers worth considering.

Note that even though your method does not introduce any bias, you still have the shortcomings of RC4, namely some detectable biases in the raw output (nothing lethal in practice, but enough to give the willies to academic cryptographers), and the absence of any IV, which means that you need a new key for every generated stream (if your messages are consecutive and serialized, you can consider them all as parts of a single big stream, but each new session / reboot MUST imply a new key; otherwise that's the infamous "two-times pad").

36 is for letters and digits; for general messaging you might want to add a few signs for spaces and basic punctuation (at least a word separator).

share|improve this answer
    
Thanks for the comments. It is possible that I might transition to a different stream cipher. RC4 was easily to implement at this stage in the prototype for testing purposes. Any thoughts on the impact on security from doing the mapping of the output, which effectively reduces the number of output values? Is there a nice statistical explanation of how the security is impacted? Thanks. –  Deskguy Nov 4 '11 at 13:08
1  
The best you can hope for, security wise, is that the generator of values in the 0..35 range is indistinguishable from uniformly random values, and the reduction you propose will get you that, assuming that you use a cryptographically secure source of bytes -- i.e. a source indistinguishable from uniformly random bytes. There is no "reduction in security". There is a kind of reduction in performance, in that you use up, on average, a bit more than 8 bits of RC4 output to get a value which fits in less than 6 bits. –  Thomas Pornin Nov 4 '11 at 13:28
    
Perfect - thanks very much for that confirmation. I had suspected that, but couldn't quite wrap my head around it - thanks for your explanation which makes sense. Agreed that there is a very minor performance hit, but in this case I'm only tossing about 1.5% of the potential values, so that doesn't concern me. Thanks for your help. –  Deskguy Nov 4 '11 at 13:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.