Title says it all… My following program is doing SHA256 hashing recursively (i.e. hashes the output of a hash etc.). The main idea is that it produces 2n series of hashes (n is denoted “SIGMA” in my program) and it needs n SHA256 strings. It works fine up to n=10 but it uses 70% SRAM, if I increase it to n=11 then the program does not output correct values (probably because it uses too much SRAM). For n=12 it displays warning about memory and does not run at all.
My main approach to save memory is to keep the initial parameters to PROGMEM (lines 16-23) and convert them to byte arrays and back to char arrays in the program (the hash function needs a string as input). However I cannot find any way to save more memory. My device is Uno (and I specifically want to run my program on this particular device only).
Any suggestions? Library used: arduinolibs/libraries/Crypto at master · rweather/arduinolibs · GitHub
Program with n=10:
#include <Crypto.h>
#include <SHA256.h>
#include <string.h>
#define HASH_SIZE 32
#define BLOCK_SIZE 64
#define OUTPUT_MAX 32
#include <limits.h> //for infinity
const unsigned int SIGMA = 10;
char hex[256];
SHA256 hash;
byte bytearray_buffer[32];
const static char* const initpebbles[] PROGMEM = {
"ef92dd53c32ceaba5db5f0a2d697cfb29b4ff250e289a5711840d40504792cda", "72d1dc06087553c571f52f057d401f9b55cce4e6b4daf531e1dfb7a6d1677989",
"39444ff9e95ed61191a477b6925215d5f3fa3e6996905e2c6b1be60d3a54673b", "b2451c6bffdd03bacd10991d59d1230909638401dc1a925de19e23caafa81824",
"2b9ce5954a44bd6e8e2fa01ddba0cf4432f5d72073c5651410e3c504cb870c27", "5acc1b260b286d203376ec75f11a97e644daad765d8b96a235e6d6e6e1f4048b",
"da205ac2f1d5a4b2029af45c6e6cbba6a21245f5b7cf6896bccd8197ab36545c", "9fabcd1fbee85dd1cb27053846ce08cf2e554351206e2a652f227c1a9d7bd13b",
"857958d158f08f168d0dad7d1bcbd5911dd2059bb5d30ec994bd9ed8fe888a93", "a665a45920422f9d417e4867efdc4fb8a04a1f3fff1fa07e998e86f7f7a27ae3"
};
char *btoh(char *dest, uint8_t *src, int len) {
char *d = dest;
while( len-- ) sprintf(d, "%02x", (unsigned char)*src++), d += 2;
return dest;
}
char* h(char* input) {
uint8_t result[32];
hash.reset();
hash.update(input, strlen(input));
hash.finalize(result, sizeof(result));
return(btoh(hex, result, 32));
}
void hexCharacterStringToBytes(byte *byteArray, char *hexString)
{
bool oddLength = strlen(hexString) & 1;
byte currentByte = 0;
byte byteIndex = 0;
for (byte charIndex = 0; charIndex < strlen(hexString); charIndex++)
{
bool oddCharIndex = charIndex & 1;
if (oddLength)
{
// If the length is odd
if (oddCharIndex)
{
// odd characters go in high nibble
currentByte = nibble(hexString[charIndex]) << 4;
}
else
{
// Even characters go into low nibble
currentByte |= nibble(hexString[charIndex]);
byteArray[byteIndex++] = currentByte;
currentByte = 0;
}
}
else
{
// If the length is even
if (!oddCharIndex)
{
// Odd characters go into the high nibble
currentByte = nibble(hexString[charIndex]) << 4;
}
else
{
// Odd characters go into low nibble
currentByte |= nibble(hexString[charIndex]);
byteArray[byteIndex++] = currentByte;
currentByte = 0;
}
}
}
}
byte nibble(char c)
{
if (c >= '0' && c <= '9')
return c - '0';
if (c >= 'a' && c <= 'f')
return c - 'a' + 10;
if (c >= 'A' && c <= 'F')
return c - 'A' + 10;
return 0; // Not a valid hexadecimal character
}
void array_to_string(byte array[], unsigned int len, char buffer[])
{
for (unsigned int i = 0; i < len; i++)
{
byte nib1 = (array[i] >> 4) & 0x0F;
byte nib2 = (array[i] >> 0) & 0x0F;
buffer[i*2+0] = nib1 < 0xA ? '0' + nib1 : 'a' + nib1 - 0xA;
buffer[i*2+1] = nib2 < 0xA ? '0' + nib2 : 'a' + nib2 - 0xA;
}
buffer[len*2] = '\0';
}
//Pebble code
//Stop function
void stop()
{
while(1);
}
typedef struct Pebble{
int StartIncr;
int DestIncr;
int position;
int destination;
byte value[32];
};
void FindValue(struct Pebble pebble_List[])
{
for (int i = 1; i < SIGMA; i++)
{
if (pebble_List[i].position == pebble_List[0].position) {
for (int j=0; j < 32; j++) {
bytearray_buffer[j] = pebble_List[i].value[j];
}
}
}
}
int struct_cmp_by_destin(const void *a, const void *b)
{
struct Pebble *ia = (struct Pebble *)a;
struct Pebble *ib = (struct Pebble *)b;
return (ia->destination - ib->destination);
}
unsigned int Pow2(byte ex)
{
return 1 << ex;
}
int x2i(char *s)
{
int x = 0;
for(;;) {
char c = *s;
if (c >= '0' && c <= '9') {
x *= 16;
x += c - '0';
}
else if (c >= 'A' && c <= 'F') {
x *= 16;
x += (c - 'A') + 10;
}
else break;
s++;
}
return x;
}
void setup()
{
Serial.begin(115200);
Pebble pebblelist[SIGMA];
for (int i = 0; i < SIGMA; i++) {
pebblelist[i].StartIncr = 3*Pow2(i+1);
pebblelist[i].DestIncr = Pow2(i+2) ;
pebblelist[i].position = Pow2(i+1);
pebblelist[i].destination = Pow2(i+1);
}
for (int i = 0; i < SIGMA; i++) {
char* ptr = (char *) pgm_read_word (&initpebbles [i]);
hexCharacterStringToBytes(pebblelist[i].value, ptr);
}
unsigned int currentposition = 0;
char temp[64] = "";
char* hashoutput;
byte temp2;
while(1) {
Serial.print("Hash ");
Serial.println(currentposition);
//1
if (currentposition >= Pow2(SIGMA) ) { stop();}
else {currentposition++ ;};
//2
for (int i = 0; i < SIGMA; i++) {
if (pebblelist[i].position != pebblelist[i].destination) {
pebblelist[i].position = pebblelist[i].position -2;
array_to_string(pebblelist[i].value, 32, temp);
hashoutput = h( h( temp ) );
hexCharacterStringToBytes(pebblelist[i].value, hashoutput);
};
}
char* output;
//3
if (currentposition % 2 == 1 ) {
array_to_string(pebblelist[0].value, 32, temp);
output = h( temp );
}
else {
array_to_string(pebblelist[0].value,32,output);
pebblelist[0].position = pebblelist[0].position + pebblelist[0].StartIncr;
pebblelist[0].destination = pebblelist[0].destination + pebblelist[0].DestIncr;
if (pebblelist[0].destination > Pow2(SIGMA) ) {
pebblelist[0].destination = INT_MAX;
pebblelist[0].position = INT_MAX;
}
else {
FindValue(pebblelist);
for (int i=0; i < 32; i++) {
pebblelist[0].value[i] = bytearray_buffer[i];
}
};
qsort(pebblelist, sizeof(pebblelist)/sizeof(pebblelist[0]), sizeof(pebblelist[0]), struct_cmp_by_destin);
};
Serial.println(output);
}
}
void loop()
{
}
