<< | Thread Index | >> ]    [ << | Date Index | >> ]

To: Hans Steegers <steegers,AT,steegers,DOT,nl>
Subject: Re: Data integrity check in CIPE - Please explain me thenecessityor benefit of a larger checksum.
From: "Eric M. Hopper" <hopper,AT,omnifarious,DOT,org>
Date: Mon, 29 Sep 2003 11:09:47 -0500
In-reply-to: <000b01c3865f$f66d9e20$d620a8c0@pcw_hans.hnsasd.priv>
Organization: Omnifarious Software
References: <000b01c3865f$f66d9e20$d620a8c0@pcw_hans.hnsasd.priv>

On Mon, 2003-09-29 at 03:02, Hans Steegers wrote:
> 1,2,5. So we need HMAC (which is encryption of the digest) for any
> improvement and the checksum size alone isn't relevant. So, we need also a
> second key. Using the same key as for encryption would make it easier to
> break that key.

Yes.  HMAC is also designed to protect against specific weaknesses that
almost all currently used message digest algorithms have.

> 3,4. I am not yet convinced here it is that easy: slightly modified packets?
> Of the non-encrypted part: yes. Of the encrypted part: you still can't
> predict the result without some insider info and it may work only for very
> limited and unlikely circumstances. Anyway, using HMAC for integrity
> checking makes this impossible.

It is relatively trivial to flip a bit in a given CBC block.  The cost
is the improper decryption of the next block.  If the CRC is on the
encrypted data, then the CRC is absolutely useless for preventing this. 
Only the internal IP and TCP/UDP checksums will help.  And they are also
susceptible to having their bits modified predictably.

For example, with CBC, if you've encrypted the following string of

The quick brown fox jumped over the lazy dog.

using a block cipher with a 64 bit block size someone who knows the
plaintext can trivially modify the ciphertext to make it decrypt to the
follow string, where X is a random value:

loseloseXXXXXXXXfox jumped over the lazy dog.

This is very dangerous.  You could, for example, systematically flip
bits in the TCP header to make all the packets go to a different port
while scrambling the first few bytes of data.  If you knew there was a
TCP stream going on, you wouldn't even have to identify the TCP packets,
you could just do it to all the packets, and the packets not part of the
TCP stream would be modified in strange ways and probably dropped, but
for many attacks this wouldn't be a problem.

If you were using CTR mode instead of CBC mode, this problems gets even
worse.  CTR mode would allow you to flip bits without the penalty of
creating random blocks of garbage.

> No, that is the wrong relation: it makes certain attacts more difficult or
> even impossible, because the packet size is no more related to the original
> packet size and the location of the contents can't be predicted. For other
> types of attacts it doesn't make a difference. There is no linear relation.

So, if I compress a 50 byte packet and a 100 byte packet, the 100 byte
packet has no chance of being distinguished from the 50 byte packet?  
In other words, will the compressed packet of 50 bytes have a 50% chance
of being larger than the compressed packet of 100 bytes?  Can you
quantify with hard numbers how much harder it would be?

When I use a protocol, I want hard, definite bounds that tell me exactly
how secure it is.  If the CIPE CRC is over the encrypted packet (which
it seems to be), then the attacker can trivially (in less than 2**8
steps) and predictably modify any block in the packet, without knowing
the key, at the cost of creating a random block following.  This isn't
very secure at all.  In fact, I would consider this criminally insecure
in a commerical system.

> Yes I have seen that, but HMAC-SHA-1 is too CPU-intensive if you are not
> using or needing all 160 bits. There must be a simpler (more balanced) way
> to 'encrypt' the message digest that is less CPU-demanding and protects the
> data integrity checking. HMAC-SHA-1 is just as CPU-demanding if you use only
> 32 bits or using all 160 of them.

Given my above analysis, simply using CRC on the encrypted packet is no
data integrity check at all.  This way, CIPE is only very slightly
better than sending your tunnel in plaintext.  I don't care how much
HMAC-SHA-1 costs, it should be an absolute requirement.

> Using HMAC-SHA-1 will make CIPE unusable on slow CPUs and/or on very fast
> media. My first guess (evaluating some implementations) is that this scheme
> is at least 1000x more CPU-demanding (and time consuming) as the current
> CRC-32.

Oh, well.  There are many fast, insecure protocols in the world.  I
don't think we need another one.

> >I've been studying cryptography and cryptographic protocols for the past
> >2-3 years.  I won't make any statements about my credentials, but I do
> >know for certain the Peter Gutman's arguments are valid, and that the
> >solution I propose will significantly improve things.
> I don't want to be rude, but why didn't you find this 'weakness' then?
> I can't imagine that somebody who studies cryptographic protocols and uses
> CIPE didn't see the use of an unprotected CRC-32 and it's weakness. The
> source was available all the time and the protocol description didn't make
> it a secret.

Partly because I didn't study the CIPE protocol with an eye towards
finding weaknesses.  Also, partly, because my experience is limited to
reading books or designing things, I'm still not that good of an
analyzer of other protocols.  It is much easier to recognize a bug when
it is pointed out than to discover it.

> P.Gutmann was at most partly right: some of his assertions were plain wrong.
> He is well regarded by some and completely ignored by others.
> The solution you suggests is valid, but overkill and would ruin CIPE's
> usability on anything but fast CPUs and slow media. We should avoid that if
> there are alternative solutions providing the same protection: speed is very
> important here.

I would guess that a K6-450 could easily handle a T1 line with
HMAC-SHA-1.  My CIPE server is an old P-90, but that will probably
change within a year.  That server actually adds (not just for CIPE) 1
or 2 milliseconds of latency to every packet.  When my latency to the
Internet as a whole is at best 40 millseconds, this isn't a big deal,
but it's still annoying.

> 1. There is no benefit in using a larger checksum. Checksum length is of no
> influence on security if no HMAC is used.

This is correct.

> 2. We need HMAC for a lighter (less cpu-demanding) message digest of say 64
> bits.
> Using SHA-1 and use only a small part of its output is overkill, a waste of
> CPU-time and would make CIPE unusable on slow CPUs and/or fast media.
> There must be a (cpu-wise) lighter (faster) solution available which also
> provides the required protection. We need this protection for a maximum of
> the dynamic key's life time. Any ideas?

If there exists a 64 bit, message digest algorithm, I'd be happy if we
used it.  It makes me nervous only using 64 bits of hash value, but for
the specific purpose of a MAC, I think it's OK.  I will look to see if
there are any faster MAC algorithms than HMAC-SHA-1 that will give 64
bits of checksum.

> 3. We need a second secret key for the HMAC, in order not to expose the
> first secret key. This is unfortunate, because it makes the configuration
> more complex.

Yes, and that key must be dynamically negotiated.  This would not (and
should not) require any increase in the secret key value in the config

Have fun (if at all possible),
There's an excellent C/C++/Python/Unix/Linux programmer with a wide
range of other experience and system admin skills who needs work.
Namely, me. http://www.omnifarious.org/~hopper/resume.html
-- Eric Hopper <hopper,AT,omnifarious,DOT,org>

Attachment: signature.asc
Description: This is a digitally signed message part

<< | Thread Index | >> ]    [ << | Date Index | >> ]