Why is my SRAM so quickly filled? There are not more than 60 bytes
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.