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.

While reading the Wiki page on RC4 I noticed that the key size must be in the range of 40–2,048 bits. So should I understand like this, that I can have a key that has length of, lets say 333 bits? (any decimal number between 40-2048?) How about inputs length?

Imagine that I can ask a user to give me an input length (for example, 1027) and keylength (lets say, 359) and I can use them?

Same question about RC2 - the key size must be in the range of 8-128 [bits] and RC5 - the key size must be in the range 0 - 2040 [bits].

Can I use any key length which is in the given range? Even the exotic one, like, I dont know, 879 or 123 bits as the length of the key?

share|improve this question
2  
pretty sure they have to be multiples of 8 bits –  calccrypto Aug 11 '13 at 21:35
1  
In principle RC4 could consume an arbitrarily long key, as long as it consists of complete bytes, but you don't gain anything once the key-size exceeds the state-size. –  CodesInChaos Aug 12 '13 at 10:55
add comment

2 Answers

Yes, you can have a key of any length of that range (as long as it is an integral number of bytes), but really, why? There is absolutely no reason to.

  • If the key is uniformly distributed, anything over 256 bits is total overkill and completely pointless.

  • If the key is not uniformly distributed (maybe it's a passphrase or something), you should not be using it directly as the RC4 key. Instead, you should hash it first (preferably using a slow hash like PBKDF2) and use the result as the RC4 key; and the output of the hash will be something like 128 bits or 256 bits, so again, the range doesn't matter.

Bottom line: If you need to ask about the exact range of key lengths, you're probably using RC4 incorrectly. Instead, stick to a key that is 128-256 bits long and is uniformly distributed and generated using a cryptographic-quality pseudorandom number generator or using a suitable hash/KDF function.


Update: apparently RC2 does allow arbitrary bit lengths for its keys, per a comment from Henno Brandsma (thanks!). However, that doesn't change the bottom line. I would not recommend using unusual length keys. Stick to ordinary lengths, like 128 bits or 256 bits.

share|improve this answer
    
I like this answer, because it gets right to the point, unlike that other long-winded guy. :) –  Brownbat Aug 26 '13 at 22:40
    
Perhaps you should reformulate the "even number of bytes" statement into, for instance, "integral number of bytes". When I read it I initially thought you meant RC4 needed a key length multiple of 16 bits and was confused. –  Thomas Aug 27 '13 at 4:09
    
Thanks, @Thomas, that's a good suggestion! I made the edit you suggested. –  D.W. Aug 27 '13 at 7:31
1  
RC2 does have a single bit resolution: it is possible to have a key of length 8 bytes (64 bits) and an effective key length (as it is called in the specification) of 42 bits, say. The RFC has some test vectors for such cases. –  Henno Brandsma Dec 11 '13 at 8:42
add comment

In short, short keys are susceptible to a certain class of attacks, key information over 2048 bits is just getting discarded, and exotic keys (those not aligned to bytes) are really either getting aligned to bytes by your implementation, or are just a very bad idea, depending.

RC4 is a fairly straightforward algorithm, let's walk through initialization to see what happens.

First, prep an incremental array of 256 bytes, say:

sbox[]
for i in 0 to 255:
  sbox.append(i)

Then take some key k and prep a separate array key_array of 256 bytes by just cycling that key to fill it up.

key_index = 0
while len(key_array) < 256:
  key_array.append(key[key_index])
  key_index = key_index + 1
  if key_index > len(key):
    key_index = 0

So anything over 2048 bits (ie, 256 bytes) gets discarded.

Now you're going to walk through these two arrays, stepping from 0 to 255, summing what you find at that index in each array, and adding that sum to a counter (mod 256). You'll then swap two values in your sbox, using that running counter as the index for one value, and your current index step as the other.

for i in 0 to 255:
  j = (j + self.sbox[i] + key_array[i]) mod 256
  swap(self.sbox[j], self.sbox[i])

Now when you're looking at the first few i's, there hasn't been much shuffling yet. Those bytes may be shuffled again later, but if you can make a few assumptions, you may be able to detect a bias between the key and the first few bytes of the sbox after initialization.

It just so happens this attack works especially well with keys 5 Bytes and under, so that's probably where the admonishment to avoid keys under 40 bits came from. Funny enough, this attack doesn't just stop at five bytes though, the probability of success drops as the key size increases, until becoming essentially impractical for keys over 16 bytes.

As for exotic keys, most simple implementations will just take bytes. So if you provide 333 bits, it's probably just interpreted as a 336 bit (42 Byte) key anyway, perhaps with a few padded 0s.

If the implementation does not pad your input to the nearest byte, and simply cycles it throughout the 2048 available bits in the key array, then you may have effectively provided a 2048 bit key. As 333 shares no common factor with 8, it would not line up with an even byte until 2668 bits, well after our key array is full. Thus, save for patterns of repetition in your 333 bit key, you may have unintentionally generated the equivalent of a 256 byte key.

As a side point, 256 bytes of key sounds great, but it's actually not buying you as much entropy as you might think. The initialization of the sbox results in filling up 256 Bytes with information, and setting two counters, i and j. The key gives you the option of filling 256 Bytes, or 255 Bytes, or 254, and so on. So 256 might not necessarily be providing any additional entropy over a key of merely 180 Bytes.

Also, note that a lot of the research involves repeated key attacks, so as DW points out, it's really important to take some step to make sure you're not repeating keys. Rivest recommends taking the (key, initialization vector) and passing that through a hash function, so even a repeated initialization vector won't lead to any relationship between subsequent keys. Another area of research examines biases in the PRNG until it has "settled." Most implementations recommend adding another value to your initialization, a number of rounds of the PRNG to discard during setup (Rivest recommends discarding the first 256 bytes).

RC4 is one of the most simple, and thus one of the most well studied stream ciphers. It's hard to keep up with all the different classes of attacks, and determine which theoretical attacks have practical applicability. So don't take this as a guarantee that RC4 will forever be safe, keep checking back on the research.

Related key attacks against large keys:

  • Chen, J., Miyaji, A. A New Practical Key Recovery Attack on the Stream Cipher RC4 Under Related-Key Model. Lecture Notes in Computer Science (LNCS), v. 6584, pp. 62-76. 2011.

  • A. L. Grosul and D. S. Wallach, A Related-key Cryptanalysis of RC4. Technical Report-00-358, Rice University Department of Computer Science. 2000. (Note: 256 Byte keys especially bad.)

Attacks against small keys using the key scheduling algorithm:

  • Paul, G., Maitra, S. Permutation After RC4 Key Scheduling Reveals the Secret Key. LNCS, v. 4876, pp. 260-377. 2007.

  • Biham, E., Carmeli, Y. Efficient Reconstruction of RC4 Keys from Internal States. LNCS, v. 5086, pp. 270-288. 2008.

  • Akgun, M., Kavak, P., Demirci, H. New Results on the Key Scheduling Algorithm of RC4. LNCS, v. 5365, pp. 40-52. 2008.

Other weaknesses

  • Fluhrer, S., Mantin, I., Shamir, A. Weaknesses in the Key Scheduling Algorithm of RC4, presented at the Eighth Annual Workshop on Selected Areas in Cryptography, 2001.

Rivest's defense of RC4

  • Rivest, R. RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4. Tech Notes, RSA Laboratories. 2002.
share|improve this answer
    
It was practical, Chen and Miyaji recovered an 86 Byte key using a standard desktop computer in about 20 hours. The weakness comes from the fact that the number of possible states for the initialized array is so much smaller than the possible keys. So when you provide a long key, it is almost always producing the same initial state as some other key. Matsui's 'Key Collisions of the RC4 Stream Cipher' provides a good overview of this class of attacks. –  Brownbat Aug 25 '13 at 15:04
    
Also, for very long keys, there are families of related keys that produce similar results for the first several 100 Bytes of keystream. The recommended patch is to discard a bunch of your initial keystream bytes before that normalizes, though I think there's ongoing debate as to how many, or if there are similar families of related keys that are much smaller. pubs.cs.rice.edu/sites/pubs.cs.rice.edu/files/… –  Brownbat Aug 25 '13 at 15:18
    
"Proper" RC4 is so easy? Sure, hash your key + IVs, that's why I cited Rivest's recommendations originally. That's not going to be practical for all implementations though. Per the refs, shorter keys make key collision searches impractical (barring chosen PT, like in the WEP crack, ie, completely different). Even so, the related keys aren't the only issue here. The PRNG doesn't have as many initial states as there are keys. At best, long keys are just providing a false sense of security. It's the same as providing more than 2048 bits, most of your information is just getting tossed anyway. –  Brownbat Aug 26 '13 at 7:24
    
I appreciate the feedback, I def need to increase my precision here. For the record, both Grosul and Miyaji agree that the difficulty of finding related key families (under some definitions of related keys) is inversely proportional to the key size. It's a strange effect, I know, but it relates to the strange relationship between periodicity and key size, as well as the fact that small keys are repeated to fill the key array, such that any small change is actually propagated multiple times. I really recommend checking out their findings. Yeah, outside the scope, though I'll edit. –  Brownbat Aug 26 '13 at 22:26
    
Brownbat, nice, I like it. +1. –  D.W. Aug 26 '13 at 23:21
add comment

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.