* [9fans] crypto question @ 2005-04-12 22:54 Tim Newsham 2005-04-12 23:10 ` boyd, rounin ` (2 more replies) 0 siblings, 3 replies; 11+ messages in thread From: Tim Newsham @ 2005-04-12 22:54 UTC (permalink / raw) To: 9fans 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/ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [9fans] crypto question 2005-04-12 22:54 [9fans] crypto question Tim Newsham @ 2005-04-12 23:10 ` boyd, rounin 2005-04-13 0:18 ` Martin Harriss 2005-04-13 19:23 ` Devon H. O'Dell 2 siblings, 0 replies; 11+ messages in thread From: boyd, rounin @ 2005-04-12 23:10 UTC (permalink / raw) To: Fans of the OS Plan 9 from Bell Labs > 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [9fans] crypto question 2005-04-12 22:54 [9fans] crypto question Tim Newsham 2005-04-12 23:10 ` boyd, rounin @ 2005-04-13 0:18 ` Martin Harriss 2005-04-13 3:36 ` Tim Newsham 2005-04-13 19:23 ` Devon H. O'Dell 2 siblings, 1 reply; 11+ messages in thread From: Martin Harriss @ 2005-04-13 0:18 UTC (permalink / raw) To: Fans of the OS Plan 9 from Bell Labs 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/ > ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [9fans] crypto question 2005-04-13 0:18 ` Martin Harriss @ 2005-04-13 3:36 ` Tim Newsham 2005-04-13 3:44 ` boyd, rounin 0 siblings, 1 reply; 11+ messages in thread From: Tim Newsham @ 2005-04-13 3:36 UTC (permalink / raw) To: Fans of the OS Plan 9 from Bell Labs > 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/ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [9fans] crypto question 2005-04-13 3:36 ` Tim Newsham @ 2005-04-13 3:44 ` boyd, rounin 2005-04-13 15:52 ` Bruce Ellis 0 siblings, 1 reply; 11+ messages in thread From: boyd, rounin @ 2005-04-13 3:44 UTC (permalink / raw) To: Fans of the OS Plan 9 from Bell Labs > 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [9fans] crypto question 2005-04-13 3:44 ` boyd, rounin @ 2005-04-13 15:52 ` Bruce Ellis 2005-04-13 18:45 ` Tim Newsham 0 siblings, 1 reply; 11+ messages in thread From: Bruce Ellis @ 2005-04-13 15:52 UTC (permalink / raw) To: Fans of the OS Plan 9 from Bell Labs 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [9fans] crypto question 2005-04-13 15:52 ` Bruce Ellis @ 2005-04-13 18:45 ` Tim Newsham 0 siblings, 0 replies; 11+ messages in thread From: Tim Newsham @ 2005-04-13 18:45 UTC (permalink / raw) To: Bruce Ellis, Fans of the OS Plan 9 from Bell Labs > 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/ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [9fans] crypto question 2005-04-12 22:54 [9fans] crypto question Tim Newsham 2005-04-12 23:10 ` boyd, rounin 2005-04-13 0:18 ` Martin Harriss @ 2005-04-13 19:23 ` Devon H. O'Dell 2005-04-13 22:01 ` Karl Magdsick 2 siblings, 1 reply; 11+ messages in thread From: Devon H. O'Dell @ 2005-04-13 19:23 UTC (permalink / raw) To: 9fans [-- 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 --] ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [9fans] crypto question 2005-04-13 19:23 ` Devon H. O'Dell @ 2005-04-13 22:01 ` Karl Magdsick 2005-04-13 22:05 ` Devon H. O'Dell 0 siblings, 1 reply; 11+ messages in thread From: Karl Magdsick @ 2005-04-13 22:01 UTC (permalink / raw) To: Fans of the OS Plan 9 from Bell Labs > 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [9fans] crypto question 2005-04-13 22:01 ` Karl Magdsick @ 2005-04-13 22:05 ` Devon H. O'Dell 2005-04-13 22:16 ` Bruce Ellis 0 siblings, 1 reply; 11+ messages in thread From: Devon H. O'Dell @ 2005-04-13 22:05 UTC (permalink / raw) To: 9fans [-- 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 --] ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [9fans] crypto question 2005-04-13 22:05 ` Devon H. O'Dell @ 2005-04-13 22:16 ` Bruce Ellis 0 siblings, 0 replies; 11+ messages in thread From: Bruce Ellis @ 2005-04-13 22:16 UTC (permalink / raw) To: Fans of the OS Plan 9 from Bell Labs 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2005-04-13 22:16 UTC | newest] Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2005-04-12 22:54 [9fans] crypto question Tim Newsham 2005-04-12 23:10 ` boyd, rounin 2005-04-13 0:18 ` Martin Harriss 2005-04-13 3:36 ` Tim Newsham 2005-04-13 3:44 ` boyd, rounin 2005-04-13 15:52 ` Bruce Ellis 2005-04-13 18:45 ` Tim Newsham 2005-04-13 19:23 ` Devon H. O'Dell 2005-04-13 22:01 ` Karl Magdsick 2005-04-13 22:05 ` Devon H. O'Dell 2005-04-13 22:16 ` Bruce Ellis
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).