AVR Freaks

The comment in the AES.ASM file explains its free for use, including commercial use. The only thing I want is to retain credit for the initial version in this source file. Anyone adding to it or modifying it should add their name as another author. You can put your version under GPL if you like. The original version will stay as is and have less requirements than even GPL.

There is a little more information in the comments about porting to different chips. My requirement of having the lower two memory address bits be zero (MOD 4 addressing) for some tables could be interesting if a C compiler or linker assigns the memory address. I suppose you could always go 3 bytes larger table size than needed and bump the address up to the first MOD 4 = 0 address.

There is also a comment about the memory size in the SubBytes and Inverse SubBytes tables (it could still stand some improvement here).

The current AES routines have already satisfied my boot loader needs, however it bugs me that the FLASH memory usage is still relatively high. The best solution I have found is trading off SRAM usage for FLASH usage. The SRAM solution generates the aes_log_xy table and aes_alog_xy table with a software algorithm and saves them in SRAM (the FLASH versions of these tables are not loaded or used). This takes 512 bytes of SRAM. Then the software overwrites the SRAM aes_log_xy table with the inverse finite field multiplication values (using both tables to generate the inverse function). Then the second table SRAM storage space is not needed and is released, so only 256 bytes of SRAM are needed for the finished inverse finite field multiplication table.

This allows the aes_sub_xy table and aes_invsub_xy table to be removed from FLASH for a much more reasonable small memory footprint. The aes_sub_bytes, aes_invsub_bytes and aes_key_expand code can all use the new SRAM table.

I have not been able to find or figure out a reasonable way to calculate a single inverse finite field multiplication on the fly, so trading off temporary use of the SRAM instead of a table in FLASH seems to be the best available solution to reduce the FLASH memory usage and still have the program run reasonably quickly.

I have been testing this version and it has been working. It does require running the code to generate the inverse finite field multiplication table first before running any key generation, encryption or decryption code. As long as the table memory in SRAM is not disturbed it can continue to be used. The extra time needed to generate the table is a small one time penalty. Using the table is a simple lookup, so it runs very efficiently. The only other thing that makes it run slower than the current aes_sub_bytes, aes_invsub_bytes and aes_key_expand code is the extra code to apply the affine to the inverse finite field multiplication result (really not all that much code, but more than my original routines).

It is possible to continue the process and convert the SRAM inverse finite field multiplication table into an aes_sub_xy table and/or an aes_invsub_xy table. Aside from the one time penalty to generate the table or tables, the program would run slightly faster then the original large memory footprint version. However, I can not think of a good reason to do this.

This new SRAM based implementation is most useful for trying to squeeze AES into a smaller AVR chip. Keep in mind that AES can also be used for pseudo random number generators, stream cyphers, hash functions and other uses beyond the boot loader. So, a squeezed down version may also be useful on larger AVR chips.

If there is any interest in this even smaller FLASH memory footprint version, I will include it in the next release?

Just a progress report. I wrote a quick test program for the small FLASH footprint SRAM based version. Without any optimization, using AES with a 256 bit key for decryption only, it was 830 bytes (415 words) of FLASH program code (this includes the 32 byte key and the setup/test code). It reported using 733 bytes of SRAM. However, 256 bytes of SRAM were used one time only for table generation, so the sustained SRAM usage is only 517 bytes (16 byte s_box, 256 byte inverse FFmult table, 240 byte expanded key and 5 bytes of variables). The key schedule expansion code had to be included since the key is expanded in SRAM to save on FLASH space.

It will not take long to clean it up and also release this small FLASH footprint version, however I do not see any point if no one shows any interest. Please let me know if anyone wants it.

So far I have had zero feedback on the actual pre-release code. My AES needs changed and I developed an implementation that uses SRAM for all four tables. This also resulted in an even smaller memory footprint implementation. Even though no one asked for it, I will include it since I have already done the work. Without any feedback I will assume the code is working and bug free. Unless there is a bug report, this one will eventually become the release “project” version.

The new code is broken into three different directories. On with primarily FLASH usage, one with primarily SRAM usage and one with a minimum memory usage footprint. The small version is a little slower, but has the most potential. I hope someone finds something useful in them. There is a new “readme.txt” file in the zip parent directory.

Sorry, I've just had my AVR from hell day and I'm running way behind. As usual, Roland Kruse from ATMEL set me straight on the AVR assembler problems I was having (thanks Roland). In response I cleaned up my pre-release code and went to test it. Well, nothing worked. My encryption and decryption failed and I started debugging against the AES test suite. I was getting really confusing debug results. So, I went back to the x1.3 release and that did not work either. Now its panic time, it appears I released bad code even though I remembered testing it first. Well I finally found out my old AT90CAN128 test chip has worn out its FLASH. Some FLASH bits deep in the expanded key schedule went bad. I replaced the chip and am now laughing about it. I'm also trying to ignore those guys in white suits with that really long sleeved jacket with the straps and buckles they want me to try on :).

Here is a cleaned up x1.4 version. The x1.3 version is still workable unless you set the KEY_FLASH on the small memory footprint implementation. I'm also including a simplified release notes text file.

DUH! I had my head stuck too far up the Rijndael/AES documentation and missed something really important :oops:. The aes_ffmult routine is only called by MixColumns and InvMixColumns. The values being multiplied are always {02}, {03}, {0E}, {0B}, {0D} or {09}. The small memory footprint aes_ffmult routine was shifting through all 8 bits when it only needed to shift through 4 bits maximum. So, the aes_mix_col and aes_invmix_col had the aes_ffmult val_a and val_b assignments swapped and the aes_ffmult loop counter was reduced from 8 to 4. This simple change took the small memory footprint implementation down to 37501 CPU cycles for encryption and 57308 cycles for decryption. Now the SMALL to SRAM comparison is:

37501 to 24598 – encrypt

56308 to 40041 – decrypt

Next I'm going to analyze the overall shift pattern per s_box[] byte and see if there is a more efficient/direct way to do the matrix multiplications in MixColumns and InvMixColumns.

Now the 2.1 times slower estimate is thrown out the window. When the new routines are finished I will get a new speed measurement.

Sorry, it looks like there will be a x1.5 pre-release after all.

raapeland,

You are absolutely correct about MixColumns and InvMixColumns being waaaay to cumbersome. While my original program was technically correct (as in it worked), I did not realize how badly it was in need of optimization until your first message got me to look at the timing. Thank you for your question. Too bad there is not an emoticon for a swift kick in my rear end :).

As mentioned in my last post, I broke down the multiplication through repeated shifts method and applied it to the specific values {02}, {03}, {0E}, {0B}, {0D} and {09}. This yielded a matrix of the sequence and minimum number of operations required for each finite field operation. My matrix results match the sequence in your C code. I just finished testing this in the SRAM version and got these results:

SRAM implementation CPU cycle results:

10467 encrypt
13222 decrypt

268 - MixColumns
480 - InvMixColumns

The aes_ffmult code has been deleted from the source as it is no longer needed. BTW, it turns out the entire MixColumns operation is used as the first half of InvMixColumns. This was not obvious to me until I saw the matrix breakdown results.

Getting rid of aes_ffmult and using this new code could have a major impact on the need for 3 different implementations. I will be making the changes and evaluating the effects today. I should post a new x1.5 version tonight. Thank you for you help.

Since there has been very little feedback and no bug reports for the current version, I will submit it as a version 1.0 release AVR project tonight.