[9fans] crypto question

[9fans] crypto question

[Tim Newsham]

Hi,
   I noticed that the libc function encrypt() uses some non-standard form 
of cipher chaining.  In the normal case one byte from the previous block 
is reencrypted with 7 bytes from the new block. Additionally there is no 
initialization vector used.

This chaining is not very strong (only slightly better than using ECB 
mode).  In particular:

   - common prefixes will encrypt the same way.
   - large common sequences within the middle or end of the
     data have a reasonable chance of encrypting the same
     way (2^-8 chance of rejoining at each encryption boundary).

These weaknesses could open the way for attacks on the code where 
encrypt() is used.  I was looking over the p9sk1 authentication and didn't 
notice any obvious attacks, but I'm not particularly good at cryptography 
(the fact that the challenge has to be matched in tickets encrypted by two 
different keys offers some protection against splicing).

Is there any reason this scheme was chosen over more traditional chaining 
modes?

Tim Newsham
http://www.lava.net/~newsham/

Re: [9fans] crypto question

[boyd, rounin]

>   I noticed that the libc function encrypt() uses some non-standard form 
> of cipher chaining.  In the normal case one byte from the previous block 

yeah that sounds right.

from:

    http://www.insultant.net/repo/des.msg

sed 's/.//' >9des.c <<'//GO.SYSIN DD 9des.c'
-/*
- *	Plan 9 DES encryption.
- */
-
-#include "des.h"
-
-int
-encrypt(void *key, void *data, int len)
-{
-	int	n;
-	int	r;
-	int	i;
-	char	*b;
-
-	if (len < DESBLOCKLEN)
-		return 0;
-
-	deskey(key);
-
-	len -= DESBLOCKLEN;
-	n = len / 7 + 1;
-	r = len % 7;
-
-	b = data;
-
-	for (i = 0; i < n; i++)
-	{
-		des(b, 0);
-		b += 7;
-	}
-
-	if (r)
-	{
-		b = data;
-		des(&b[len], 0);
-	}
-
-	return 1;
-}
-
-/*
- *	Plan 9 DES decryption.
- */
-int
-decrypt(void *key, void *data, int len)
-{
-	int	n;
-	int	r;
-	int	i;
-	char	*b;
-
-	if (len < DESBLOCKLEN)
-		return 0;
-
-	deskey(key);
-
-	len -= DESBLOCKLEN;
-	n = len / 7 + 1;
-	r = len % 7;
-
-	b = data;
-
-	if (r)
-		des(&b[len], 1);
-
-	b = &b[len - r];
-
-	for (i = 0; i < n; i++)
-	{
-		des(b, 1);
-		b -= 7;
-	}
-
-	return 1;
-}
-
-/*
- *	Convert a Plan 9 key to a DES key.
- */
-uchar	*
-des9key(uchar *key)
-{
-	int		i;
-	int		m1[]	= { 0x00, 0x01, 0x03, 0x07, 0x0F, 0x1F, 0x3F };
-	int		m2[]	= { 0x00, 0xFC, 0xF8, 0xF0, 0xE0, 0xC0, 0x80 };
-	static uchar	nkey[DESKEYPLEN];
-
-	nkey[0] = key[0] & 0xFE;
-
-	for (i = 1; i < 7; i++)
-		nkey[i] = (key[i - 1] & m1[i]) << 8 - i | (key[i] & m2[i]) >> i;
-
-	nkey[7] = (key[6] & 0x7F) << 1;
-
-
-	return nkey;
-}
-
-/*
- *	Securenet challenge encryption.
- */
-int
-netcrypt(void *key, void *data)
-{
-	uchar	b[DESBLOCKLEN];
-
-	strncpy((char *)b, (char *)data, DESBLOCKLEN);
-
-	if (!encrypt(des9key(key), b, DESBLOCKLEN))
-		return 0;
-
-	sprint((char *)data, "%.2ux%.2ux%.2ux%.2ux", b[0], b[1], b[2], b[3]);
-	return 1;
-}
-
-/*
- *	Map a hexadecimal string to Securenet decimal string.
- */
-void
-sechex(char *buf)
-{
-	char	*p;
-
-	for (p = buf; *p != '\0'; p++)
-	{
-		switch (*p)
-		{
-		case 'A':
-		case 'B':
-		case 'C':
-		case 'a':
-		case 'b':
-		case 'c':
-			*p = '2';
-			break;
-
-		case 'D':
-		case 'E':
-		case 'F':
-		case 'd':
-		case 'e':
-		case 'f':
-			*p = '3';
-			break;
-		}
-	}
-}
//GO.SYSIN DD 9des.c

--
MGRS 31U DQ 52572 12604

Re: [9fans] crypto question

[Martin Harriss]

Done to please the export controllers, methinks.  From the 2nd edition 
ENCRYPT(2) man page:

BUGS
The source is not included in the public distributions. The 
implementation is broken in a way that makes it unsuitable for anything 
but authentication.

Martin


Tim Newsham wrote:
> Hi,
>   I noticed that the libc function encrypt() uses some non-standard form 
> of cipher chaining.  In the normal case one byte from the previous block 
> is reencrypted with 7 bytes from the new block. Additionally there is no 
> initialization vector used.
> 
> This chaining is not very strong (only slightly better than using ECB 
> mode).  In particular:
> 
>   - common prefixes will encrypt the same way.
>   - large common sequences within the middle or end of the
>     data have a reasonable chance of encrypting the same
>     way (2^-8 chance of rejoining at each encryption boundary).
> 
> These weaknesses could open the way for attacks on the code where 
> encrypt() is used.  I was looking over the p9sk1 authentication and 
> didn't notice any obvious attacks, but I'm not particularly good at 
> cryptography (the fact that the challenge has to be matched in tickets 
> encrypted by two different keys offers some protection against splicing).
> 
> Is there any reason this scheme was chosen over more traditional 
> chaining modes?
> 
> Tim Newsham
> http://www.lava.net/~newsham/
> 

Re: [9fans] crypto question

[Tim Newsham]

> Done to please the export controllers, methinks.  From the 2nd edition 
> ENCRYPT(2) man page:
>
> BUGS
> The source is not included in the public distributions. The implementation is 
> broken in a way that makes it unsuitable for anything but authentication.

If this is the case, should this be switched now that export restrictions
have eased?

> Martin

Tim Newsham
http://www.lava.net/~newsham/

Re: [9fans] crypto question

[boyd, rounin]

> If this is the case, should this be switched now that export restrictions
> have eased?

'spose so.  i quite liked the CBC tho.  guess it hints what the NSA
could bust, rather than J. Random Idiot.
--
MGRS 31U DQ 52572 12604

Re: [9fans] crypto question

[Bruce Ellis]

I think it's a mute point. "unsuitable for anything
but authentication" is fair, but it is suitable for p9sk1.

If you really wanta try a man-in-the-middle attack you'll
need more resources than the user is willing to wait for.

If you are just snooping you won't learn anything to
compromise the authenticated session or shared key.

Correct me if I'm wrong.

brucee

On 4/13/05, boyd, rounin <boyd@insultant.net> wrote:
> > If this is the case, should this be switched now that export restrictions
> > have eased?
> 
> 'spose so.  i quite liked the CBC tho.  guess it hints what the NSA
> could bust, rather than J. Random Idiot.
> --
> MGRS 31U DQ 52572 12604

Re: [9fans] crypto question

[Tim Newsham]

> I think it's a mute point. "unsuitable for anything
> but authentication" is fair, but it is suitable for p9sk1.
>
> If you really wanta try a man-in-the-middle attack you'll
> need more resources than the user is willing to wait for.
>
> If you are just snooping you won't learn anything to
> compromise the authenticated session or shared key.
>
> Correct me if I'm wrong.

If it is "suitable for authentication" then there's no problem.
I have definitely not figured out a way to abuse the weaknesses
to break the authentication.  My concern is that weaknesses like
this often provide an avenue for an attack and my failure to come
up with one is definitely not a proof that one doesn't exist.
Why use a weak form of chaining that offers an attacker some
extra leverage when stronger forms exist, are well known and
widely examined?

> brucee

Tim Newsham
http://www.lava.net/~newsham/

Re: [9fans] crypto question

[Devon H. O'Dell]

[-- Attachment #1: Type: text/plain, Size: 1996 bytes --]

On Tue, Apr 12, 2005 at 12:54:20PM -1000, Tim Newsham wrote:
> Hi,
>   I noticed that the libc function encrypt() uses some non-standard form 
> of cipher chaining.  In the normal case one byte from the previous block 
> is reencrypted with 7 bytes from the new block. Additionally there is no 
> initialization vector used.
> 
> This chaining is not very strong (only slightly better than using ECB 
> mode).  In particular:
> 
>   - common prefixes will encrypt the same way.
>   - large common sequences within the middle or end of the
>     data have a reasonable chance of encrypting the same
>     way (2^-8 chance of rejoining at each encryption boundary).

Indeed, this provides means for so-called `birthday attacks' in
which repeating characters can be guessed which may help an
attacker gain further knowledge of the plaintext or key by 
effectively reducing the effort necessary to brute force (at
least part of) the plaintext.

> These weaknesses could open the way for attacks on the code where 
> encrypt() is used.  I was looking over the p9sk1 authentication and didn't 
> notice any obvious attacks, but I'm not particularly good at cryptography 
> (the fact that the challenge has to be matched in tickets encrypted by two 
> different keys offers some protection against splicing).

Doesn't p9sk1 still use DES? DES was nice, but has several
recognized ways to speed up cryptanalysis of the algorithm. 3DES
is an alternative, but with combinations such as Rijndael-256 in
CBC mode (or indeed, using a strong stream cipher -- Helix looks
neat, but it's still too new, I think), I really don't see why
we should stick with these things.

Of course, we can discuss this all we want, but without code it
remains a bikeshed :)

> Is there any reason this scheme was chosen over more traditional chaining 
> modes?
> 
> Tim Newsham
> http://www.lava.net/~newsham/

Perhaps just due to simplicity of implementation? I dunno :).

--Devon

[-- Attachment #2: Type: application/pgp-signature, Size: 194 bytes --]

Re: [9fans] crypto question

[Karl Magdsick]

 > Doesn't p9sk1 still use DES? DES was nice, but has several
> recognized ways to speed up cryptanalysis of the algorithm. 3DES
> is an alternative, but with combinations such as Rijndael-256 in
> CBC mode (or indeed, using a strong stream cipher -- Helix looks
> neat, but it's still too new, I think), I really don't see why
> we should stick with these things.

FYI, sufficiently useful quadratic approximations (XSL attack) of AES
exist to reduce all key lengths of AES to equivalent of no more than
128-bit strength.  These attacks will likely be improved in the
future.  The same class of attacks reduces Serpent to no more than
equivalent 192-bit key strength.  The key-dependent substitution
tables used in TwoFish appear to make it immune to this sort of
attack.  If you're going to pick an AES finalist block cipher, TwoFish
now appears to be the strongest of the AES finalists (especially the
legally unencumbered ciphers), despite Rijndael being chosen for AES.


-Karl

Re: [9fans] crypto question

[Devon H. O'Dell]

[-- Attachment #1: Type: text/plain, Size: 1305 bytes --]

On Wed, Apr 13, 2005 at 06:01:36PM -0400, Karl Magdsick wrote:
>  > Doesn't p9sk1 still use DES? DES was nice, but has several
> > recognized ways to speed up cryptanalysis of the algorithm. 3DES
> > is an alternative, but with combinations such as Rijndael-256 in
> > CBC mode (or indeed, using a strong stream cipher -- Helix looks
> > neat, but it's still too new, I think), I really don't see why
> > we should stick with these things.
> 
> FYI, sufficiently useful quadratic approximations (XSL attack) of AES
> exist to reduce all key lengths of AES to equivalent of no more than
> 128-bit strength.  These attacks will likely be improved in the
> future.  The same class of attacks reduces Serpent to no more than
> equivalent 192-bit key strength.  The key-dependent substitution
> tables used in TwoFish appear to make it immune to this sort of
> attack.  If you're going to pick an AES finalist block cipher, TwoFish
> now appears to be the strongest of the AES finalists (especially the
> legally unencumbered ciphers), despite Rijndael being chosen for AES.
> 
> -Karl

Aha, that's quite interesting to know. Do you have any
information about attacks on Serpent (which also appears to be
quite strong, at least from what its webpage would have you
believe)?

--Devon

[-- Attachment #2: Type: application/pgp-signature, Size: 194 bytes --]

Re: [9fans] crypto question

[Bruce Ellis]

Anyone thought off a computationally feasable attack that
disproves  the"unsuitable for anything but authentication"
claim?  Check out the protocol, the time frame, what
is exchanged and how it is subsequently used.

brucee