Why is my SRAM so quickly filled? There are not more than 60 bytes I have just gone through all my code. At max I use 60 bytes. I have done everything in order to minimize its usage - I even store booleans as bits, not bytes! What could be happening here?

The only thing that comes to my mind are extremely large arrays, like this:

const uint8_t SBoxes[8][4][16] PROGMEM;


However, these are stored in the program memory as you can see. How can I check they are really there and my memory usage? My code is too large to post it here.

EDIT:

IDE tells me (even though I believe it's very inaccurate):


  Sketch uses 7,898 bytes (24%) of program storage space. Maximum is 32,256 bytes.
  Global variables use 1,023 bytes (49%) of dynamic memory, leaving 1,025 bytes for local variables. Maximum is 2,048 bytes.


All my literal strings use F() and there are not many of them.

EDIT2:

Code on pastebin. Just for a quick glance, it is really large.

EDIT3:

My Serial prints

ready
some numbers (that's ok I ask it to print out an array)
ENready
again numburs
Enready
...


I ask it to print ready at the very beginning of my program. I ask it to println End of encr near the end of my setup funciton, but as you see it never finishes the printing.

It always behaves like that when I run out of SRAM.
When you are asking yourself what is eating so much RAM, the first step
is to look at the symbol table in the ELF file. If you use a makefile, you
probably know where to find the ELF file. If you are using the Arduino
IDE, go to File / Preferences, check “Show verbose output during
compilation”, compile and look at the output: you will see the temporary
directory where the compiler puts your ELF file.

Now run the command avr-nm -Crtd --size-sort your_elf_file and look
for symbols of type 'D' (data), 'V' (vtable) and 'B' (BSS), in either
upper or lower case. On a Unix-style OS you would pipe through
grep -i ' [dbv] '. Running this on your program gives:

00000068 B tx_buffer
00000068 B rx_buffer
00000034 B Serial
00000021 B lcd
00000016 V vtable for HardwareSerial
00000008 V vtable for LiquidCrystal
00000004 B timer0_overflow_count
00000004 B timer0_millis
00000002 D __malloc_margin
00000002 D __malloc_heap_start
00000002 D __malloc_heap_end
00000002 B __flp
00000002 B __brkval
00000001 b timer0_fract
00000001 D encr
00000001 B debug
00000001 B EEPROM


Obviously, this cannot account for the 1,023 bytes of static RAM your
program is using. What this command misses is the literal arrays and
strings. These can be seen with the command
avr-objdump -j .data -s your_elf_file. The literal strings are quite
obvious in the output, the literal arrays less so. Running this on your
program gives a long listing starting with

Contents of section .data:
800100 00000005 2000010e 040d0102 0f0b0803  .... ...........
800110 0a060c05 09000700 0f07040e 020d010a  ................


Now, on the source code we see:

const uint8_t SBoxes[8][4][16] PROGMEM = {
{{14,  4,  13,  1,   2, 15,  11,  8,   3, 10,   6, 12,   5,  9,   0,  7},
 { 0, 15,   7,  4,  14,  2,  13,  1,  10,  6,  12, 11,   9,  5,   3,  8},
 { 4,  1,  14,  8,  13,  6,   2, 11,  15, 12,   9,  7,   3, 10,   5,  0},
 {15, 12,   8,  2,   4,  9,   1,  7,   5, 11,   3, 14,  10,  0,   6, 13} },
 ...


If you translate this to hexadecimal, you get 0e 04 0d 01 02 0f...,
which appears also by the end of the first line of previous listing. So
there is your culprit: all the big PROGMEM arrays. The compiler does not
honor the PROGMEM attribute on local variables.

My first thought was to make the arrays global, and this does solve the
problem. However, as pointed out by Mikael Patel in a comment, the
documentation on PROGMEM states that “variables must be either globally
defined, OR defined with the static keyword, in order to work with
PROGMEM.” Then, making the arrays static const PROGMEM is a cleaner
solution.