String Encryption (encoding)

[Magialisk]

Phew, it turned out the MixColumns() function was quite a bit more of a pain than I gave it credit for. What I initially categorized as "a simple matrix multiplication with special rules about carrying" turned out to be completely off base. Instead the operation relies on multiplication over the Rijndael Galois field, so I was quickly back to being the non-math major who doesn't know what a "Galois field" even means.

I strongly considered hard-coding pre-computed constants for all the possible multiplications, but it turns out that would ahve required six lookup tables with 255 values each to cover multiplying by 2, 3, 9, 11, 13 and 14. Even I draw the line at hand typing over 1500 "set /a thing[n]=0xValue" entries, so I had no choice but to fnd an algorithm and code it.

It turns out the code ended up pretty small:

Code: Select all

::define 'GaloisMult' macro
::takes two multiplicands as inputs plus a variable name in which to store the product over the Rijndael Galois field
set macro.GaloisMult=do (%\n%
  setlocal enableDelayedExpansion%\n%
  set /a "multA=(%%~a)"%\n%
  set /a "multB=(%%~b)"%\n%
  set "product=0"%\n%
  set "carry=0"%\n%
  for /l %%n in (1,1,8) do (%\n%
    set /a "lsbtest=!multB!^&0x01"%\n%
    if !lsbtest!==1 set /a "product=!product!^^!multA!"%\n%
    if !product! GTR 255 set /a "product=!product!-256"%\n%
    set /a "carry=!multA!^&0x80"%\n%
    set /a "multA=!multA!<<1"%\n%
    if !multA! GTR 255 set /a "multA=!multA!-256"%\n%
    if not !carry!==0 set /a "multA=!multA!^^0x1b"%\n%
    set /a "multB=!multB!>>1"%\n%
  )%\n%
  for %%v in (!product!) do endlocal^&set "%%~c=%%v"%\n%
)

That macro does what it says, and I spot-checked it against a reasonable number of values from online pre-computed tables, so it should be good to go. It could be optimized by breaking out of the FOR loop early if either multiplicand reaches 0, but I couldn't figure out how to break a FOR loop that is part of a macro definition? Does anyone have any tips there?

I tried adding "if !multA!==0 for %%v in (!product!) do endlocal^&set "%%~c=%%v"%\n%" at the top, along with the same check against MultB, and it "seems" to work (the correct product comes back) but I get a bunch of "missing operand" errors as the loop continues to expand in the background instead of actually breaking. I tried to append "^& exit" to the above line, which closes my whole CMD window, and I tried making a label just above the product return at the bottom and doing a GOTO at the top of the loop when A or B are 0, but that doesn't break at all and instead I get "setlocal has reached it maximum level of recursion" (whoops! )

Optimizing the macro by breaking early isn't exactly life or death, I just figure if we have to run all 16 elements of the state through 8 loop iterations per round, over 10 rounds, thats ~1300 loop iterations. And that's per every 128-bits of data we want to encrypt, so the number of loops could add up quick... It would be nice if the bytes that only needed 1-2 loops before hitting 0 would break early instead of wasting time doing 6-7 more empty loops. If anyone has any ideas I'd love to hear them. Thanks!

[Magialisk]

Well I'm officially halfway there. The encryption operation is now working, tested against the example values in the FIPS-197 standard. As expected it's pretty darn slow, though I haven't done anything intentional to optimize it, and I'm still looking for an answer to breaking a FOR loop inside a macro to speed up the Galois multiplication...

Using the standard test values it encrypted 128-bits in 1.81 seconds.

Code: Select all

C:\BTP\AES>aes
Output data: 3925841D02DC09FBDC118597196A0B32
Elapsed Time:  00:00:01.81

I can optionally have it output a bunch of debugging data as well that shows the values at every step along the way. Here's an example of that data:

Code: Select all

C:\BTP\AES>set aes_debug=1 & aes
input key: 2B7E151628AED2A6ABF7158809CF4F3C
input data: 3243F6A8885A308D313198A2E0370734

Expanded round keys:
round 1 key: A0FAFE1788542CB123A339392A6C7605
round 2 key: F2C295F27A96B9435935807A7359F67F
round 3 key: 3D80477D4716FE3E1E237E446D7A883B
round 4 key: EF44A541A8525B7FB671253BDB0BAD00
round 5 key: D4D1C6F87C839D87CAF2B8BC11F915BC
round 6 key: 6D88A37A110B3EFDDBF98641CA0093FD
round 7 key: 4E54F70E5F5FC9F384A64FB24EA6DC4F
round 8 key: EAD27321B58DBAD2312BF5607F8D292F
round 9 key: AC7766F319FADC2128D12941575C006E
round 10 key: D014F9A8C9EE2589E13F0CC8B6630CA6

Initial AddRoundKey result: 193DE3BEA0F4E22B9AC68D2AE9F84808

Begin round #1:
SubBytes result:    D42711AEE0BF98F1B8B45DE51E415230
ShiftRows result:   D4BF5D30E0B452AEB84111F11E2798E5
Galois*2 result:    B365BA60DB73A4476B8222F93C4E2BD1
Galois*3 result:    67DAE7503BC7F6E9D3C333082269B334
MixColumns result:  046681E5E0CB199A48F8D37A2806264C
Round key:          A0FAFE1788542CB123A339392A6C7605
AddRoundKey result: A49C7FF2689F352B6B5BEA43026A5049

Begin round #2:
SubBytes result:    49DED28945DB96F17F39871A7702533B
ShiftRows result:   49DB873B453953897F02D2F177DE961A
Galois*2 result:    92AD15768A72A609FE04BFF9EEA73734
Galois*3 result:    DB76924DCF4BF58081066D089979A12E
MixColumns result:  584DCAF11B4B5AACDBE7CAA81B6BB0E5
Round key:          F2C295F27A96B9435935807A7359F67F
AddRoundKey result: AA8F5F0361DDE3EF82D24AD26832469A
.
.
.
Begin round #9:
SubBytes result:    87EC4A8CF26EC3D84D4C46959790E7A6
ShiftRows result:   876E46A6F24CE78C4D904AD897ECC395
Galois*2 result:    15DC8C57FF98D5039A3B94AB35C39D31
Galois*3 result:    92B2CAF10DD4328FD7ABDE73A22F5EA4
MixColumns result:  473794ED40D4E4A5A3703AA64C9F42BC
Round key:          AC7766F319FADC2128D12941575C006E
AddRoundKey result: EB40F21E592E38848BA113E71BC342D2

Begin round #10:
SubBytes result:    E9098972CB31075F3D327D94AF2E2CB5
ShiftRows result:   E9317DB5CB322C723D2E895FAF090794
Galois*2 result:    15DC8C57FF98D5039A3B94AB35C39D31<-- same as round 9
Galois*3 result:    92B2CAF10DD4328FD7ABDE73A22F5EA4<-- same as round 9
MixColumns result:  E9317DB5CB322C723D2E895FAF090794<-- same as ShiftRows
Round key:          D014F9A8C9EE2589E13F0CC8B6630CA6
AddRoundKey result: 3925841D02DC09FBDC118597196A0B32

Output data: 3925841D02DC09FBDC118597196A0B32
Elapsed Time:  00:00:06.37

Decryption requires coding the inverses of each of the four round operations, so there's still plenty to be done, but if you can write code forward you can write it backwards, right?

[Magialisk]

No progress as of yet on the decryption side of the algorithm, though I did tweak the encryption to be considerably faster.

I have no idea why but it seems my scripts are often significantly slower on my Win7 PC than my XP PC. This was no exception, as the exact same operation that I posted yesterday that took 1.81s on a WinXP machine took 6.92s on Win7. In debug mode (which took 19.72s in Win7!) there was a noticeable pause of at least a second every time the script hit the Galois multiplication calculations.

I decided that the only hope for this script ever being usable was to get rid of the real-time Galois calculations and hard-code the pre-computed values as lookup tables, just like I'd done for the Sbox before. Fortunately, instead of having to type out 1500+ table entries by hand, I was able to write a short script to repeatedly call my GaloisMult macro and echo the results to a file in a nicely formatted lookup table.

In case anyone's interested, here's the script that I used to generate the six required tables:

Code: Select all

FOR %%n IN (2 3 9 11 13 14) DO (
   FOR /L %%a IN (0,5,250) DO (
      set /a p1=%%a+1
      set /a p2=%%a+2
      set /a p3=%%a+3
      set /a p4=%%a+4
      %macro_call% ("%%n %%a out") %macro.GaloisMult%
      %macro_call% ("!out! hex") %macro.Num2Hex%
      set Galois[%%a]=!hex!
      %macro_call% ("%%n !p1! out") %macro.GaloisMult%
      %macro_call% ("!out! hex") %macro.Num2Hex%
      set Galois[!p1!]=!hex!
      %macro_call% ("%%n !p2! out") %macro.GaloisMult%
      %macro_call% ("!out! hex") %macro.Num2Hex%
      set Galois[!p2!]=!hex!
      %macro_call% ("%%n !p3! out") %macro.GaloisMult%
      %macro_call% ("!out! hex") %macro.Num2Hex%
      set Galois[!p3!]=!hex!
      %macro_call% ("%%n !p4! out") %macro.GaloisMult%
      %macro_call% ("!out! hex") %macro.Num2Hex%
      set Galois[!p4!]=!hex!
      FOR %%b IN (!p1!) DO FOR %%c IN (!p2!) DO FOR %%d IN (!p3!) DO FOR %%e IN (!p4!) DO (
         echo set /a G%%n[%%a]=0x!Galois[%%a]! ^& set /a G%%n[%%b]=0x!Galois[%%b]! ^& set /a G%%n[%%c]=0x!Galois[%%c]! ^& set /a G%%n[%%d]=0x!Galois[%%d]! ^& set /a G%%n[%%e]=0x!Galois[%%e]!>> GaloisTables.txt
      )
   )
   %macro_call% ("%%n 255 out") %macro.GaloisMult%
   %macro_call% ("!out! hex") %macro.Num2Hex%
   echo set /a G%%n[255]=0x!hex!>> GaloisTables.txt
)
GOTO:EOF

The tables take up a LOT of space (~33.5 KB - going back to that time/memory tradeoff discussion), but at least they're clean and tidy and I didn't have to type them . Here's a sample snippet from where one ends and the next begins:

Code: Select all

set /a G2[240]=0xFB & set /a G2[241]=0xF9 & set /a G2[242]=0xFF & set /a G2[243]=0xFD & set /a G2[244]=0xF3
set /a G2[245]=0xF1 & set /a G2[246]=0xF7 & set /a G2[247]=0xF5 & set /a G2[248]=0xEB & set /a G2[249]=0xE9
set /a G2[250]=0xEF & set /a G2[251]=0xED & set /a G2[252]=0xE3 & set /a G2[253]=0xE1 & set /a G2[254]=0xE7
set /a G2[255]=0xE5
set /a G3[0]=0x00 & set /a G3[1]=0x03 & set /a G3[2]=0x06 & set /a G3[3]=0x05 & set /a G3[4]=0x0C
set /a G3[5]=0x0F & set /a G3[6]=0x0A & set /a G3[7]=0x09 & set /a G3[8]=0x18 & set /a G3[9]=0x1B
set /a G3[10]=0x1E & set /a G3[11]=0x1D & set /a G3[12]=0x14 & set /a G3[13]=0x17 & set /a G3[14]=0x12

With these tables copied into the main AES script, I rewrote the MixColumns function to simply perform a lookup/substitution instead of calculating the Galois product on the fly. Re-running the encryption test on my Win7 PC now takes only 0.74s, a reduction of nearly 90% . I have a couple other less impressive optimizations in mind that I want to try out, and then at some point I'll have to write the decryption side of the cipher...

[jeb]

Hi Magialisk,

very nice to see that a working AES algorithm is possible with batch files.

The Galois lookup tables are a good solution, and I suppose that it's the normal way to use them.
I only avoid lookup tables in some of my small embedded projects with little memory.

The initialisation of the sboxes could be a bit smaller.

Code: Select all

set ^"sbox=637C777BF26B6FC53001672BFED7AB76CA82C97DFA5947F0ADD4A2AF9CA472C0B7FD9326363FF7CC34A5E5F171D8311504C723C31896059A071280E2EB27B275^
09832C1A1B6E5AA0523BD6B329E32F8453D100ED20FCB15B6ACBBE394A4C58CFD0EFAAFB434D338545F9027F503C9FA851A3408F929D38F5BCB6DA2110FFF3D2^
CD0C13EC5F974417C4A77E3D645D197360814FDC222A908846EEB814DE5E0BDBE0323A0A4906245CC2D3AC629195E479E7C8376D8DD54EA96C56F4EA657AAE08^
BA78252E1CA6B4C6E8DD741F4BBD8B8A703EB5664803F60E613557B986C11D9EE1F8981169D98E949B1E87E9CE5528DF8CA1890DBFE6426841992D0FB054BB16"
setlocal EnableDelayedExpansion
for /L %%n in (0 1 255) Do (
   set /a pos=%%n*2
   for %%p in (!pos!) do set "val=!sbox:~%%p,2!"
   set /a Sbox[%%n]=0x!val!
)

jeb

[Magialisk]

Thanks jeb for that tip! That's similar to how I built the Galois tables but I didn't think to store only long strings and transform them into tables at the start of execution.

In fact at first looking at your code I was thinking "nah, I don't want to run a bunch of extra for loops at the start of the program to generate all my tables". I was envisioning someone running AES in a loop, creating a new setlocal each time, and every time it starts it has to re-expand the tables, etc.

Then I had a potential revelation. What if I just said screw the tables and kept the values in the single long strings. Why bother expanding them at all? Here's what my current one-liner looks like for the SubBytes operation, using the Sbox lookup table (previously renamed S[]):

Code: Select all

FOR /L %%b IN (0,1,3) DO FOR /L %%c IN (0,1,3) DO FOR %%d IN (!state[%%b][%%c]!) DO set /a state[%%b][%%c]=!S[%%d]!

Using your suggestion, I could change the one-liner to the below and the only difference is two extra set statements per loop at runtime:

Code: Select all

FOR /L %%b IN (0,1,3) DO FOR /L %%c IN (0,1,3) DO FOR %%d IN (!state[%%b][%%c]!) DO (
   set /a pos=2*%%d
   FOR %%e IN (!pos!) DO set "val=!sbox:~%%e,2!"
   set /a "state[%%b][%%c]=0x!val!"
)

I gave this a whirl and it works great. I really do like the concept, but of course it slows down execution slightly due to the long string parse. I ran the script three times each way and got these results:

Code: Select all

Original one-liner FOR:  0.76s, 0.72s, 0.79s
Modified parsing FOR:   0.94s, 0.89s, 0.94s

The cost of the shortened Sbox definition was anywhere from 100ms to 220ms, and if I wanted to do this for the Galois tables as well they'd surely add another ~150ms each. It's too bad because I love the concept, but I can't spare the execution time. As is I'm only running about 21 Bytes/sec on my Win7 machine (nearly 3 ascii characters per second), so a 1KB file should take about a minute to encrypt, allowing some time for ascii->hex pre-conversion.

I'll be the first to admit this is realistically only an educational/demonstration/"look what batch can do" exercise vs. anything ultimately practical, but for now I want to aim for speed wherever it's easy to find... Thanks again for both your tip and your encouragement. I'll report back with full source once I get decryption coded.

[Magialisk]

I got peeved off at a "Format String Vulnerability" lab I'm supposed to be working on so I blew off some steam by coding the decryption side of my AES cipher this afternoon:

Code: Select all

C:\Users\Marc\Desktop>aes enc
Test Data=00112233445566778899aabbccddeeff
Test Key=000102030405060708090a0b0c0d0e0f
Output data: 69C4E0D86A7B0430D8CDB78070B4C55A
Elapsed Time:  00:00:00.69

C:\Users\Marc\Desktop>aes dec
Test Data=69c4e0d86a7b0430d8cdb78070b4c55a
Test Key=000102030405060708090a0b0c0d0e0f
Output data: 00112233445566778899AABBCCDDEEFF
Elapsed Time:  00:00:00.70

So as is right now it's good to go for 128-bit keys and 128-bit (32-char) hex blocks. You could conceivably run it in a loop and pass it 32 characters per iteration and have the equivalent of Electronic Codebook (ECB) mode. I still have a lot of other features in mind that sound interesting, tweaking the key schedule and number of rounds to support 192- and 256-bit keys, file encryption (and more importantly, reassembly from decrypted hex to ascii), CBC/CTR modes, etc.

If anyone is interested in seeing the code let me know. It's still a bit sloppy as I'm adding things frequently, but the core of the cipher code is short and sweet so I could extract that out easily enough.

[Magialisk]

Let it be said that the 256-bit version of the key scheduling algorithm was a pain in my rear. Nothing like MixColumns(), but not friendly either. Not only that, but all the additional logic of checking "is this a 256-bit key", "is this word number a half-multiple vs. a full-multiple" etc. slowed my execution down by about 200ms. I'm going to have to dig in a bit and see if anything can be optimized, but at least 192- and 256-bit keys are now supported on the encode side. I'll have to go back and tweak the decode side to support them, as it's currently still hard-coded for 10 cipher rounds. It should only take a few minutes based on the minor changes required on the encode side, but it's quite late so I'm calling it a night.

Code: Select all

C:\Users\Marc\Desktop>aes enc
Test Data=00112233445566778899aabbccddeeff
Test Key=000102030405060708090a0b0c0d0e0f
Output data: 69C4E0D86A7B0430D8CDB78070B4C55A
Elapsed Time:  00:00:00.92

C:\Users\Marc\Desktop>aes enc
Test Data=00112233445566778899aabbccddeeff
Test Key=000102030405060708090a0b0c0d0e0f1011121314151617
Output data: DDA97CA4864CDFE06EAF70A0EC0D7191
Elapsed Time:  00:00:01.08

C:\Users\Marc\Desktop>aes enc
Test Data=00112233445566778899aabbccddeeff
Test Key=000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f
Output data: 8EA2B7CA516745BFEAFC49904B496089
Elapsed Time:  00:00:01.19