Problem with the RC6 algorithm in Source Code Forum

[John Gleason]

I posted a fix for a significant error in the the RC6 algorithm posted in the Source Code Forum found here:

RC6 algorithm

I'm unsure how much the error damages the security of RC6, but it is probably significant and possibly catastrophic, so I thought it worth fixing. Especially since I've nearly finished testing an optimization of it that is quite fast and may be of interest to some.

[Mike Trader]

Thanks John. I just posted that code because it was the only one of all the Encryption Algos I tested that required some work to implement. I thought I might as well contribute it.

It is not a good choice as far as I am concerned, but others seem to want it.

What is does do, is demonstrate the method for padding the input string. This is a common need with block ciphers. The method pads the fibal block with CHR$(0) then appends a single byte with the count of pad bytes coded as an ASCII character (0-255)

The original code was from Wonsky I believe. What was the "significant error" you corrected?

[John Gleason]

The original code was from Wonsky I believe. What was the "significant error" you corrected?

The error is/was a multiply overflow problem, and very well may go back to the beginning Wonsky Lu port. (see detailed explanation in corrected source post). You may also want to take a look at the optimized version I am testing, which I will post asap. RC6 wasn't selected for the AES, true, but I find it a little easier to understand than the Rijndael algo, and its optimized speed isn't too bad.

[John Gleason]

Okay, the updated and highly tested optimized RC6 algorithm is now posted at:

http://www.powerbasic.com/support/pb...ad.php?t=35265

[Mike Trader]

Dont forget to test it with some known test vectors:

    sTestFile   = "00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
    sTestKey    = "00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
    sTestCipher = "8f c3 a5 36 56 b1 f7 78 c1 29 df 4e 98 48 a4 1e"
                                                         
    sTestFile   = "02 13 24 35 46 57 68 79 8a 9b ac bd ce df e0 f1"
    sTestKey    = "01 23 45 67 89 ab cd ef 01 12 23 34 45 56 67 78"
    sTestCipher = "52 4e 19 2f 47 15 c6 23 1f 51 f6 36 7e a4 3f 18"
                                                       
    sTestFile   = "00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
    sTestKey    = "00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
    sTestCipher = "6c d6 1b cb 19 0b 30 38 4e 8a 3f 16 86 90 ae 82"

    sTestFile   = "02 13 24 35 46 57 68 79 8a 9b ac bd ce df e0 f1"
    sTestKey    = "01 23 45 67 89 ab cd ef 01 12 23 34 45 56 67 78 89 9a ab bc cd de ef f0"
    sTestCipher = "68 83 29 d0 19 e5 05 04 1e 52 e9 2a f9 52 91 d4"

    sTestFile   = "00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
    sTestKey    = "00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
    sTestCipher = "8f 5f bd 05 10 d1 5f a8 93 fa 3f da 6e 85 7e c2"

    sTestFile   = "02 13 24 35 46 57 68 79 8a 9b ac bd ce df e0 f1"
    sTestKey    = "01 23 45 67 89 ab cd ef 01 12 23 34 45 56 67 78 89 9a ab bc cd de ef f0 10 32 54 76 98 ba dc fe"
    sTestCipher = "c8 24 18 16 f0 d7 e4 89 20 ad 16 a1 67 4e 5d 48"

Also, I noticed a padding error for 16byte files. I corrected this in the cource code forum

[John Gleason]

>>Dont forget to test it with some known test vectors

Yes, good point. I have tested it extensively only with itself, that is, do encode, do decode, check decode with original file, if identical then all is correct, continue to next file to test.

Now with the test parameters, I can also see if my "correction" that I posted is actually right, or if the zero overflows are intentional and my "fix" is wrong and has to be removed. (no big deal to do programmatically, but youch, I may have to eat crow here ). First tho, I have to apply your padding fix, because I'm getting too many encrypted characters in the cyphertext.

[John Gleason]

Mike, I have been unable to get either your or my version to match the test vectors. Do you have an example that matches?

[John Gleason]

Perhaps a note to Aleksandr Dobrev, if you're following this thread, have you got code matching the results of the RC6 test vectors? I can't get my or Mike's code to match the published ciphertext results.
eg.

    sTestFile   = "02 13 24 35 46 57 68 79 8a 9b ac bd ce df e0 f1"
    sTestKey    = "01 23 45 67 89 ab cd ef 01 12 23 34 45 56 67 78"
    sTestCipher = "52 4e 19 2f 47 15 c6 23 1f 51 f6 36 7e a4 3f 18"

[Aleksandr Dobrev]

Perhaps a note to Aleksandr Dobrev

John, Mike I'm really on fire with current job, I hope in a week or week and half I'll able back to forum's life and will check RC6 again, year ago I just did straight translation from C, not completely line by line because a lot of that C code was designed as universal for various hardware, so I replace some code with short PB operators in some cases. I compare returned result of original C code with PB and it bring the same results. Will check it again when I get a little bit spare time. BTW, I found original C code made by R. Rivest on MIT's site, will check it too with control vectors.

[Mike Trader]

>Mike, I have been unable to get either your or my version to match the test vectors.
ok. I did not test it

>Do you have an example that matches?
I am not using this algo so I am not interested in making it comply. I used it only as a reference for comparing speed of other algos that have been adopted by AES.

[John Gleason]

Aleksandr, I thought about it a while, and tested my theory as to where the error might be, and got lucky because the test vectors I checked matched after I made the code changes. There turned out to be a couple problems: 1) the dword zero overflows I previously mentioned and fixed in earlier posts (so that crow dinner will be postponed at least for a while), and 2) a key schedule divisor of apparently bit reference rather than dword reference (was 32, should be 4).

So, you don't have to spend time debugging it after all. But thanks for the offer anyway. My mind wouldn't quit thinking about the dad burn thing until it somehow solved it. Btw, ending like that in a solution is by no means the normal result of such ruminations. :shhh:

I'll post the fixed and now verified (and very speedy) code shortly.

[John Gleason]

And finally, here is that code.

http://www.powerbasic.com/support/pb...903#post267903