Re: IEEE 802.11 WEP holes

[Nikita Borisov]

"R. A. Hettinga" writes:
>At 9:35 AM -0800 2/5/01, Jurgen Botz wrote:
>> Slashdot this morning reported on a ZD-Net article at:
>>
>>http://www.zdnet.com/zdnn/stories/news/0,4586,2681947,00.html?chkpt=zdhpnews0
>> 1
>> which states that there are major holes in IEEE 802.11 "WEP" encryption.
>>
>> Does anyone have any more details on this?
>
>http://www.vmeng.com/mc/debrief00.html, and grep for WEP, although Vinnie
>hasn't gotten the slides from Nikita Borosov yet, it looks like, but I bet
>they'll be there soon, now :-)...

More info on our findings can be found at 
   

The slides from Mac Crypto (with minor edits) are at the bottom of that
web page; sorry for not sending them in earlier.

- Nikita

Re: IBM press release - encryption and authentication

[Nikita Borisov]

Ray Dillinger writes:
>>I may be misunderstanding what you are suggesting, but the construction
>>that uses an encrypted CRC as a MAC is insecure.  Eg. Stubblebine &
>>Gligor[1] show attacks on protocols which encrypt the concatenation of a
>>packet and a CRC-32 using DES-CBC.  The properties of the MAC, encrypted
>>or not, do appear to matter.
>
>Yeah.  The problem with an encrypted CRC is that it's relatively 
>easy to find another plaintext that has the same CRC, hence you 
>can substitute a different set of bits for the document. 

Actually, there are problems even if you use a function that does not
have this property.  There is a general attack, which David Wagner just
pointed out to me, that applies even if we use a collision-resistant
hash function instead: suppose your authenticating code is
encrypt(m||H(m)), where H is a hash function.  Then there is a
chosen-message attack that asks the sender to encrypt&authenticate the
message m=m'||H(m')||pad.  Then, by taking a prefix of the message, the
attacker has a valid authentication on the message m'.  Now, this is a
bit of an esoteric attack, but it does violate the security conditions
of a MAC.

My point is that a CRC, or even an unkeyed hash function, does not
guarantee authenticity, only integrity.  Similarly, encrypting something
does not guarantee authenticity, only secrecy, because it may be
possible to get an encryption of what you want in a different context.
Jutla's proof of security goes to some length to ensure that this does
not occur with reasonable probability.

- Nikita

Re: IBM press release - encryption and authentication

[Nikita Borisov]

In article <010801c064d0$b64193a0$6000a8c0@em>,
Enzo Michelangeli <[EMAIL PROTECTED]> wrote:
>Apart from the parallelization-friendliness, wouldn't the same result be
>achieved by encrypting the concatenation of the plaintext with a MAC
>implemented through a fast error detection code (say, a sufficiently long
>CRC)? Due to the presence of encryption, the security properties of the
>inner MAC don't appear to really matter (as they would in the "DES-CBC
>first, then HMAC-MD5" scenario mentioned in the draft for comparison).

I may be misunderstanding what you are suggesting, but the construction
that uses an encrypted CRC as a MAC is insecure.  Eg. Stubblebine &
Gligor[1] show attacks on protocols which encrypt the concatenation of a
packet and a CRC-32 using DES-CBC.  The properties of the MAC, encrypted
or not, do appear to matter.

I think, though, that the "parallelization-friendliness" of the result
is much more interesting than being able to encrypt and MAC at the same
time.

- Nikita

[1] "On Message Security in Cryptographic Protocols", IEEE Symposium on
Security & Privacy, Oakland 1992.

Re: IBM press release - encryption and authentication

[Nikita Borisov]

Greg Rose writes:
>At 05:14 PM 12/11/2000 -0800, Nikita Borisov wrote:
>>But in his examples, addition mod 2^128 - 159 can be implemented rather
>>quickly:
>>
>>S_i = S_{i-1} + b [regular 128-bit addition]
>>if (b > S_i) S_i += 159
>
>Ahhh, yes, a classical example of premature optimisation. This is, of 
>course, a different definition of modular arithmetic than most people would 
>use.

Well, it _does_ find a number congruent to S_{i-1} + b mod (2^128-159),
which is one definition of modular addition.  But you're right -- unless
both sides are using this version of the algorithm, a final reduction is
necessary to find a representation in the range [0,2^128-159).  I should
have looked at his slides more carefully...

- Nikita

Re: IBM press release - encryption and authentication

[Nikita Borisov]

In article <[EMAIL PROTECTED]>,
Bram Cohen  <[EMAIL PROTECTED]> wrote:
>it's not hard to figure it out just from the slides - there are actually
>two methods given, one which requires an extra lg(n) encryptions and one
>which requires two extra encryptions but has a bunch of modular
>arithmetic. Rijndael is so fast I suspect the second one might not prove
>all that useful.

But in his examples, addition mod 2^128 - 159 can be implemented rather
quickly:

S_i = S_{i-1} + b [regular 128-bit addition]
if (b > S_i) S_i += 159

- Nikita