Q: SAC
in [Cryptography]
|
Prev: RSA key size and safety
Next: MBOL AAOT MBCL LUAT MKAT
From: Mok-Kong Shen on 4 Oct 2009 15:10 Maaartin wrote: > On Sep 30, 10:03 pm, g...(a)nope.ucsd.edu (Greg Rose) wrote: [snip] > For the 4x4 matrix you're right, since there's be always a cycle > (consider the columns as vertices and the two ones in a row as an edge > between them). In general, either you're wrong or my program is buggy > (which is quite possible, even the regularity test may be wrong): > > SIZE 2: > 10 > 01 > SIZE 6: > 110010 > 010101 > 001101 > 000111 > 100011 > 100101 > SIZE 10: > 1010001101 > 1110010010 > 0111010010 > 0101011100 > 1011110000 > 1010010110 > 1001101001 > 1011000110 > 0100100111 > 0100001111 > SIZE 18: > 110001000101110101 > 010011110100111000 > 001111010000111010 > 000101111110001001 > 000011111101100010 > 010001001011101110 > 010000100111011110 > 010000110111111000 > 000001011110110110 > 001001100110101101 > 001010010011011011 > 000000011101110111 > 000011101000111101 > 111011000110010001 > 100110010010001111 > 100011010010001111 > 101111000000100111 > 110101000100110011 > SIZE 14: > 11010100011001 > 01000111010101 > 00100101001111 > 01011011100010 > 00101010100111 > 00010101100111 > 10000011111100 > 00110001001111 > 11000010111100 > 01000011010111 > 00111100001101 > 10000100110111 > 01001001010111 > 00010100110111 > SIZE 22: > 1001100100101100111001 > 0111010101101000010110 > 1010011110100111000010 > 0001110110010111000110 > 1000100010010011110111 > 0011011000001110111001 > 1001111101100001000110 > 0000000111111110111000 > 0011000011011001101101 > 1010110001000110011011 > 1010001010111110010100 > 0111011001010011000101 > 0100011000011101110101 > 1100001000000101111111 > 0000001000011111110111 > 1000111001000101010111 > 0000101000011010111111 > 0100010101110010011110 > 1001010001010001111101 > 1100100100111100000111 > 1100110100101000011011 > 0000011110110001001111 > SIZE 26: > 10100011110010000110001111 > 01000110011011100111011000 > 01111110101110000001010001 > 01010000010011101110101101 > 00001111010101011110000110 > 10100111001110000010001111 > 00100010010011110111110010 > 00001001110111110001001101 > 10001000111011010011010110 > 00100000111010111011000111 > 00010000001111011001110111 > 00001101011101010011010011 > 00001001100010101111111100 > 00010011001101010110011110 > 00101001100001111000111011 > 10101010100001011111110000 > 00001011110000101011011110 > 00100000001110001101111111 > 11100101010010000011101110 > 10001000000101010101111111 > 00100111110000000110111011 > 00100001011000110111111010 > 01100010111101001000001111 > 01100010001101110001001111 > 11100000101110011001000111 > 00101110011011110101000001 > SIZE 30: > 110001010111000001110000111011 > 011000011100111101111100000001 > 001011101111110010000001101001 > 100100001101100001111111100100 > 000010101100001101111011011010 > 000011011001101111001110010001 > 000000110000011011100101111111 > 101100010000111011001001011110 > 000110001001111000011101101011 > 010000100110110011011100101110 > 001000110011010011100111101001 > 000100110001010110101111001101 > 000010110010111011010001011110 > 000010010011010110111100010111 > 101000000001101010110011110111 > 100010001100010100111100111110 > 100000000001110011111011101011 > 101010100101000011101100011101 > 010100100100000010111011111011 > 001100010001100001110010111111 > 100010101000000010011111101111 > 011000001000110101001111111100 > 010001001101011010010011110101 > 000100100101110010010101011111 > 001100011000001110100101101111 > 000011110001111111001000011010 > 110100101000001110010001011111 > 000110010001100110100110101111 > 010000110100100111101000111011 > 110000010101111110101001001001 > > I implemented something like you proposed, I add ones randomly in a > column until the're enough of them while checking bijectivity after > each step (in case of a singular matrix I remove the last one and > retry). It found the above results but nothing more for sizes up to > 32. It looks like it works only for sizes of the form 2+4*n with > integer n>=0. Your matrix for n=6 cannot be right. For the vectors 000000 and 010000 give on multiplication with the matirx 000000 and 110000 respectively. That is, flipping one bit (here the 2nd bit) of the input causes 2 bits of the output (the 1st and the 2nd bit) to flip. We require however n/2 = 3 bits to be flipped. It is rather easy to see that, in order to satisfy the requirement of flipping one input bit always leading to flipping of exactly n/2 output bits, all columns of the matrix have to have exactly n/2 zeros and n/2 ones. This is not fulfilled by your n=6 matrix and also some others (e.g. your n=10). So I strongly believe that your program must have a bug. A non-singular matrix for n=6 satisfying the requirment is the following, which I found with a program of mine: 111110 111101 100011 010011 001000 000100 In a previous post I stated: 2) For n = 0 (mod 2) n != 0 (mod 4) the existence of such linear bijective functions has been verified up to n = 30 and it seems very plausible that this is indeed a general result. There the phrase 'verified up to n = 30' was based on your result. So, to be correct, I have to retract that. But the existence for n=6 seems to be ensured by my result above. (I have carefully checked my result and should be very surprised, if it were wrong.) BTW, I have found for n=8 a (non-linear) bijective function such that flipping 1 input bit causes at least 3 and at most 4 bits of the output to flip. (As Fluhrer has elegantly shown, to have always exactly 4 output bits flipped is impossible in this case.) See a recent post of mine in the thread 'Avalanche measure' for the function I found. Thanks, M. K. Shen
From: Maaartin on 4 Oct 2009 18:11 On Oct 4, 9:10 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Maaartin wrote: ... > Your matrix for n=6 cannot be right. For the vectors 000000 and > 010000 give on multiplication with the matirx 000000 and 110000 > respectively. That is, flipping one bit (here the 2nd bit) of > the input causes 2 bits of the output (the 1st and the 2nd bit) > to flip. We require however n/2 = 3 bits to be flipped. It is > rather easy to see that, in order to satisfy the requirement of > flipping one input bit always leading to flipping of exactly > n/2 output bits, all columns of the matrix have to have exactly > n/2 zeros and n/2 ones. This is not fulfilled by your n=6 matrix > and also some others (e.g. your n=10). So I strongly believe that > your program must have a bug. It's quite possible, it has, but.... did you try to transpose the matrix? There're exactly 3 ones in each row. But sure, it's a bug. Btw., did you tried to find such a matrix having exactly n/2 ones in both each row and each column? > 2) For n = 0 (mod 2) n != 0 (mod 4) the existence of such linear > bijective functions has been verified up to n = 30 and it seems very > plausible that this is indeed a general result. > > There the phrase 'verified up to n = 30' was based on your result. > So, to be correct, I have to retract that. But the existence for > n=6 seems to be ensured by my result above. (I have carefully > checked my result and should be very surprised, if it were wrong.) I didn't check my results (I was glad to get it running since it was quite late for me). I'd bet it's correct (up to transposition), but I wouldn't bet much money. > BTW, I have found for n=8 a (non-linear) bijective function such > that flipping 1 input bit causes at least 3 and at most 4 bits > of the output to flip. (As Fluhrer has elegantly shown, to have > always exactly 4 output bits flipped is impossible in this case.) > See a recent post of mine in the thread 'Avalanche measure' for > the function I found. It's interesting... but wouldn't be better to search for easy-to- implement highly non-linear functions instead? I looks like such a search is non-trivial even for n=4 (see the changes in http://www.sdl.hitachi.co.jp/crypto/luffa).
From: Mok-Kong Shen on 4 Oct 2009 19:19 Maaartin wrote: > On Oct 4, 9:10 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: >> Maaartin wrote: ... >> Your matrix for n=6 cannot be right. For the vectors 000000 and >> 010000 give on multiplication with the matirx 000000 and 110000 >> respectively. That is, flipping one bit (here the 2nd bit) of >> the input causes 2 bits of the output (the 1st and the 2nd bit) >> to flip. We require however n/2 = 3 bits to be flipped. It is >> rather easy to see that, in order to satisfy the requirement of >> flipping one input bit always leading to flipping of exactly >> n/2 output bits, all columns of the matrix have to have exactly >> n/2 zeros and n/2 ones. This is not fulfilled by your n=6 matrix >> and also some others (e.g. your n=10). So I strongly believe that >> your program must have a bug. > > It's quite possible, it has, but.... did you try to transpose the > matrix? > There're exactly 3 ones in each row. But sure, it's a bug. The transpose is o.k. > Btw., did you tried to find such a matrix having exactly n/2 ones in > both each row and each column? No. >> 2) For n = 0 (mod 2) n != 0 (mod 4) the existence of such linear >> bijective functions has been verified up to n = 30 and it seems very >> plausible that this is indeed a general result. >> >> There the phrase 'verified up to n = 30' was based on your result. >> So, to be correct, I have to retract that. But the existence for >> n=6 seems to be ensured by my result above. (I have carefully >> checked my result and should be very surprised, if it were wrong.) > > I didn't check my results (I was glad to get it running since it was > quite late for me). > I'd bet it's correct (up to transposition), but I wouldn't bet much > money. If the condition of n/2 ones and zeros in each column is satisfied and the matrix is nonsingular, then the requirement is satisfied. You could do a simple fix of your program and check that yourself. I think currently that that would very likely come out o.k. >> BTW, I have found for n=8 a (non-linear) bijective function such >> that flipping 1 input bit causes at least 3 and at most 4 bits >> of the output to flip. (As Fluhrer has elegantly shown, to have >> always exactly 4 output bits flipped is impossible in this case.) >> See a recent post of mine in the thread 'Avalanche measure' for >> the function I found. > > It's interesting... but wouldn't be better to search for easy-to- > implement highly non-linear functions instead? I looks like such a > search is non-trivial even for n=4 (see the changes in > http://www.sdl.hitachi.co.jp/crypto/luffa). I can't access that page at all. I suppose one should investigate any crypto functionality from as many aspects as possible and not capitalize on a particular one, even that one may be in some sense more important. Avalanche is presumably a comparatively primitive (simple) concept, I don't exactly know, since I am a layman. M. K. Shen
From: Maaartin on 4 Oct 2009 20:19 On Oct 5, 1:19 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Maaartin wrote: > > I'd bet it's correct (up to transposition), but I wouldn't bet much > > money. > > If the condition of n/2 ones and zeros in each column is satisfied > and the matrix is nonsingular, then the requirement is satisfied. > You could do a simple fix of your program and check that yourself. > I think currently that that would very likely come out o.k. Sure... the number of ones is fine after the transposition, the only problem could be the bijectivity. It passed a small test I wrote. It found no solution for even n. So I'm happy with it for now. > I can't access that page at all. Neither I can now, but it worked at the time of my last posting. Obviously there're redirecting to https now (for whatever reason). Try https://www.sdl.hitachi.co.jp:443/crypto/luffa/ look at "Specification Version 2.0 (15 Sep. 2009)", pages 14 and 23 "Supporting document (15 Sep. 2009)", pages 6-7, 10-11 > I suppose one should investigate > any crypto functionality from as many aspects as possible and not > capitalize on a particular one, even that one may be in some sense > more important. Avalanche is presumably a comparatively primitive > (simple) concept, I don't exactly know, since I am a layman. I'm layman too, but I'd say it's hardly simpler than LDMax and LPMax and much less important. Look at http://www.engr.mun.ca/~howard/Research/Papers/ldc_tutorial.html In case you find it complicated, just try to understand "Table 4. Linear Approximation Table" and "Table 7. Difference Distribution Table" - computing them is no harder than evaluating avalanche.
From: Mok-Kong Shen on 5 Oct 2009 04:58
Maaartin wrote: > Sure... the number of ones is fine after the transposition, the only > problem could be the bijectivity. > It passed a small test I wrote. It found no solution for even n. So > I'm happy with it for now. I don't quite understand your problem. The bijectivity is in this case the same as the non-singularity of the matrix, which however is particularly easy to check with gaussian elimination, since the matrix is boolean. > Neither I can now, but it worked at the time of my last posting. > Obviously there're redirecting to https now (for whatever reason). Try > https://www.sdl.hitachi.co.jp:443/crypto/luffa/ > look at "Specification Version 2.0 (15 Sep. 2009)", pages 14 and 23 > "Supporting document (15 Sep. 2009)", pages 6-7, 10-11 > I'm layman too, but I'd say it's hardly simpler than LDMax and LPMax > and much less important. Look at > http://www.engr.mun.ca/~howard/Research/Papers/ldc_tutorial.html > In case you find it complicated, just try to understand "Table 4. > Linear Approximation Table" and "Table 7. Difference Distribution > Table" - computing them is no harder than evaluating avalanche. Doing the computation of the avalanche measure for the function like the one I found -- I mean when the function is given -- is actually very straightforward and fast. Thus I don't see why this apparently useful information about any such functions used in crypto should be ignored. Thanks, M. K. Shen |