Najmniejsza implementacja AES dla mikrokontrolerów?

38

Czy ktoś może polecić małą, bezpłatną implementację AES-128 Rijndael dla mikrokontrolerów. Idealnie, dla PIC18, choć ogólna implementacja w C byłaby przydatna.

Kompilacja implementacji axTLS dla PIC18 i szyfrowanie / deszyfrowanie bloku wymaga 6KB ROM i 750b RAM.

Kompilacja rijndael-alg-fst.c dla PIC18 i szyfrowanie / deszyfrowanie bloku wymaga 28 KB ROM i 0,5 KB RAM.

Kompilowanie 8-bitowego AES Briana Gladmana dla PIC18 i szyfrowanie / deszyfrowanie bloku wymaga 19 KB pamięci ROM i 190 bajtów pamięci RAM.

Czy są dostępne lepiej zoptymalizowane warianty PIC?

(zaktualizowane wymagania dotyczące pamięci RAM dla wersji axTLS)

Toby Jaffey
źródło
1
Czy to dla bootloadera?
Daniel Grillo,
Nie, dotyczy aplikacji sieciowej
Toby Jaffey,
Microchip ma implementację dla dsPIC i PIC 24, która ma rozmiar kodu 3018 bajtów, ale miała tylko szyfrowanie, bez deszyfrowania. Zgadnięcie, że to nie jest dla ciebie.
Kellenjb 21.04.11
@Kellenjb Ciekawe, ale szukam czegoś małego na 8-bitowe
mikroskopy
1
@mikeselectricstuff Tak, musi to być AES. Próbuję współpracować z istniejącym systemem za pomocą AES-128. Interesuje mnie każda mała implementacja AES, ale obecnie celuję w PIC18. Używam kompilatora HiTech Pro picc18.
Toby Jaffey

Odpowiedzi:

19

Zastanawiam się, jak udało ci się uzyskać 7,5kB użycia pamięci RAM z axTLS. Patrząc na kod, cały kontekst jest przechowywany w tej strukturze:

typedef struct aes_key_st 
{
    uint16_t rounds;
    uint16_t key_size;
    uint32_t ks[(AES_MAXROUNDS+1)*8];
    uint8_t iv[AES_IV_SIZE];
} AES_CTX;

Rozmiar tej struktury to 2 + 2 + 4 * 15 * 8 + 16 = 504. Nie widzę żadnych zmiennych globalnych w aes.c, wszystkie zmienne automatyczne są małe, więc użycie stosu jest również uzasadnione. Gdzie więc idzie 7,5kB? Być może próbujesz wykorzystać całą bibliotekę zamiast po prostu wypakować z niej implementację AES?

W każdym razie ta implementacja wygląda dość prosto, wolałbym trzymać się tego kodu i spróbować go zoptymalizować. Wiem, że może to być trudne, ale poznanie szczegółów AES może pomóc przynajmniej oszacować absolutne minimalne zużycie pamięci RAM.

Aktualizacja: Właśnie próbowałem skompilować tę bibliotekę na Linuksie IA-32 i napisać prosty test szyfrowania CBC AES-128. Otrzymałem następujące wyniki (pierwsza liczba to szesnastka długości sekcji):

 22 .data         00000028  0804a010  0804a010  00001010  2**2
                  CONTENTS, ALLOC, LOAD, DATA
 23 .bss          00000294  0804a040  0804a040  00001038  2**5
                  ALLOC

To tylko 660 bajtów .bss (zadeklarowałem AES_CTX jako zmienną globalną). Większość .data jest zajęta przez IV i klucz. Nie dołączam tutaj .text, ponieważ uzyskasz zupełnie inny wynik na PIC (sekcje danych powinny mieć prawie taki sam rozmiar na obu architekturach).

Malarze kodów
źródło
Źle odczytałem współczynnik 10 w wersji axTLS. Masz rację. Ale nadal interesują mnie bardziej wydajne wersje AES ...
Toby Jaffey,
5
Wydajny pod względem wielkości lub prędkości? Jakie właściwie są ograniczenia? Pamiętaj, że mniejsze biblioteki będą prawdopodobnie wolniejsze - jeśli spojrzysz na kod źródłowy większych (pod względem sekcji kodu) bibliotek, większość wzdęć wynika z wcześniej obliczonych stałych tablic.
Code Painters,
1
Pod względem wielkości pamięci RAM i ROM. Szybkość nie jest problemem, ale staram się wcisnąć wiele funkcji w małe urządzenie.
Toby Jaffey,
14

Wiem, że to pytanie jest trochę stare, ale niedawno musiałem je zbadać, ponieważ wdrażam AES128 na PIC16 i 8051, więc też byłem ciekawy tego pytania.

Użyłem czegoś takiego: http://cs.ucsb.edu/~koc/cs178/projects/JT/aes.c, a moje użycie pamięci RAM to kilkaset bajtów, a rozmiar binarny jest mniejszy niż 3kb ROM.

Moja najlepsza rada to przeczytać na stronie Wikipedii http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation i zrozumieć różne tryby, na przykład, w jaki sposób AES w trybie OFB wykorzystuje tryb EBC jako podstawowy element konstrukcyjny. Również XOR'ing (w trybie OFB) sprawia, że ​​jest to symetryczna operacja, więc szyfrowanie / deszyfrowanie to ta sama funkcja, która również oszczędza miejsce.

Kiedy zrozumiałem, jak naprawdę działa AES, mogłem zaimplementować go w C, a następnie przetestować pod kątem specyfikacji NIST ** (zrób to! Dużo kodu znalezionego online jest wadliwy) i zaimplementuj tylko to, czego absolutnie potrzebowałem.

Dzięki temu dostosowaniu i optymalizacji mogłem dopasować AES128 do 8051 wraz z innym oprogramowaniem RF. Zużycie pamięci RAM (dla całego systemu) spadło z ~ 2,5 kb do nieco poniżej 2 kb, co oznacza, że ​​nie musieliśmy aktualizować do 8051 z SRAM 4 kb, ale mogliśmy nadal korzystać z tańszej wersji SRAM 2 kb.

** Wektory testowe znajdują się w załączniku F w: http://csrc.nist.gov/publications/nistpubs/800-38a/addendum-to-nist_sp800-38A.pdf

EDYTOWAĆ:

W końcu dostałem kod na Github: https://github.com/kokke/tiny-AES-c

Zoptymalizowałem trochę rozmiar. Wielkość wyjściowa GCC po skompilowaniu dla ARM:

$ arm-none-eabi-gcc -O2 -c aes.c -o aes.o
$ size aes.o
   text    data     bss     dec     hex filename
   1024       0     204    1228     4cc aes.o

Wykorzystanie zasobów wynosi teraz 1KB, 204 bajty RAM.

Nie pamiętam, jak budować dla PIC, ale jeśli 8-bitowy AVR Atmel Mega16 jest podobny do PIC, użycie zasobów jest następujące:

$ avr-gcc -Wall -Wextra -mmcu=atmega16 -O2 -c aes.c -o aes.o
$ avr-size aes.o
   text    data     bss     dec     hex filename
   1553       0     198    1751     6d7 aes.o

Więc 1,5K kodu i 198 bajtów pamięci RAM.

Morten Jensen
źródło
Zastanawiam się, jak będzie się układać implementacja, którą wykonałem w 2001 roku . Nie generuje S-boxów; są statyczne.
Kaz
6

Niedawno wziąłem implementację axTLS i pracowałem nad zmniejszeniem jej tak bardzo, jak tylko mogłem. Możesz łatwo samodzielnie wygenerować S-boxy i zaoszczędzić kilkaset bajtów.

static uint8_t aes_sbox[256];   /** AES S-box  */
static uint8_t aes_isbox[256];  /** AES iS-box */
void AES_generateSBox(void)
{
    uint32_t t[256], i;
    uint32_t x;
    for (i = 0, x = 1; i < 256; i ++)
    {
        t[i] = x;
        x ^= (x << 1) ^ ((x >> 7) * 0x11B);
    }

    aes_sbox[0] = 0x63;
    for (i = 0; i < 255; i ++)
    {
        x = t[255 - i];
        x |= x << 8;
        x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
        aes_sbox[t[i]] = (x ^ 0x63) & 0xFF;
    }
    for (i = 0; i < 256;i++)
    {
         aes_isbox[aes_sbox[i]]=i;
    }
}

Pełne źródło można uzyskać pod adresem : http://ccodeblog.wordpress.com/2012/05/25/aes-implementation-in-300-lines-of-code/

Andrzej
źródło
Znasz swoje rzeczy, Andrew. Pozytywne. : D
Alex
3

Robiłem implementację tylko w C, AES-128, o nazwie aes-min , z licencją MIT. Jest skierowany do małych mikroprocesorów (np. 8-bitowych) z małą ilością pamięci RAM / ROM.

Ma opcjonalne obliczanie harmonogramu kluczy w locie, aby zmniejszyć wymagania dotyczące pamięci (unikając potrzeby pełnego rozszerzonego harmonogramu kluczy w pamięci RAM).

Craig McQueen
źródło
1

Ta implementacja może być dla Ciebie interesująca. Jest z krypto-biblioteki AVR typu open source.

Można znaleźć ogólne (nieaktualna) informacje i dane statystyczne dotyczące wielkości i wydajności kodu tutaj .

AES:

Informacje o AES

Bawiłem się tylko źródłem SHA-1 z tej biblioteki, więc nie mogę komentować AES.

Rev1.0
źródło
0

Najmniejszy AES128, który napisałem dla serii PIC, może działać w 900 instrukcjach i 42 bajtach pamięci RAM. Używam go sam w serii PIC12, ale PIC10F206 jest również możliwy :-).

Nie mogę ujawnić kodu, ponieważ pochodzi on od mojej firmy, ale napisałem go w asm dla serii PIC10-12-16. Szyfrowanie zajmuje 444 bajty kodu, w tym tablicę wyszukiwania 256 bajtów, kod ten zawiera również funkcję ładowania klucza, która ma około 25 bajtów.

Radziłbym wszystkim sprawdzić dokument AES i sam go wdrożyć! Większość implementacji jest bardzo zła i używa zbyt wiele pamięci RAM i ROM.

Zaimplementowałem również AES128 dla dsPIC i PIC24 i używam około 70% mniej miejsca w kodzie w porównaniu do lib microchip, a mój kod jest również nieco szybszy. Numery implementacji dsPIC i PIC24:

„Szyfrowanie zajmuje około 2995 cykli. 79,10uS @ 40 MIPS, 197,75uS @ 16 MIPS”

„DecKeySetup zajmuje około 567 cykli. 14,20uS @ 40 MIPS, 35,43uS @ 16 MIPS”

„Deszyfrowanie zajmuje około 3886 cykli. 97,15uS przy 40 MIPS, 242,88uS przy 16 MIPS”

„Całkowity rozmiar kodu to 1050 słów łącznie z tabelami”.

Piękno rdzenia PIC24 polega na tym, że niektóre instrukcje mają 32 bity, co znacznie ułatwia życie przy budowie małej implementacji AES128, mój kod używa wszystkich dostępnych instrukcji 32-bitowych i jest całkowicie 32-bitowy, więc mogę szybko przenieść kod do PIC32 lub inne 32-bitowe procesory.

AES jest bardzo prosty do wdrożenia, tylko większość ludzi nawet nie próbuje!

Spójrz na link: http://www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf

PaulHolland
źródło
Czy to jest oprogramowanie typu open source? Czy możesz opublikować kod?
Toby Jaffey,
2
@Paul - Witamy w inżynierii elektrycznej! Twoja odpowiedź jest interesująca i zachęcająca, ale nie jest tak naprawdę użyteczna bez dalszych szczegółów. 900 instrukcji może prawdopodobnie zmieścić się w bloku kodu! Kliknij link „edytuj” pod odpowiedzią, aby go poprawić.
Kevin Vermeer
@PaulHolland wspaniałe wiadomości, gdzie jest kod?
Frank
2
@Paul - Otrzymasz stos pozytywnych ocen zamiast głosowania, które obecnie posiadasz, jeśli wyjaśnisz, jak to napisałeś i opublikowałeś kod! Jeśli nie możesz opublikować kodu ze względów licencyjnych, przynajmniej wyjaśnij, jak go napisałeś i jak Joby może równolegle z twoją pracą.
Kevin Vermeer