Now that you know what a hash function is you may be wondering why use one. The most common use of a hashing function is to store data that is sorted by a key. We could use something fairly unique in the data for the key, say a person’s name. Given a person’s name, we can generate an integer hash value using our hashing function and then use that integer as a key to an array position. What we have made is called a hash table. Since names are variable length, the hashing function reduced the key complexity down to an integer. However, names can be duplicated (since people can have the same name), so sometimes our hash table may have collisions. Therefore, we would need to deal with this somehow in our records, but for the most part it is an easy way to store and lookup data quickly.

Hashing functions can also be used to determine if data has been altered. A common algorithm for this is CRC32. This algorithm is designed to detect common transmission errors in data (such as the flipping of a single bit). Data is transmitted with a CRC code. The receiver then takes the data and calculates its own CRC and checks it against the received CRC. If they are different, either the data was altered (or the CRC was changed). Either way, the data needs to be sent again.

Lastly, hashing algorithms are used in cryptography to verify the integrity of data. Like CRC, the concept is similar: take the received data, hash it, and check it against a known hash to see if it has been altered. Unlike CRC, though, these hashes usually also rely on a digital signature or authentication code that is based on a private key. In these cases the hash needs to have this additional information since a malicious user can forge both the message and the hash code.

Now that we covered the basics of hashing functions, let’s talk about hashing in Legato. As of Legato 1.1g, there are two hashing algorithms available. The first is a simple hash known as DJB2, and the second is a cryptographic hash MD5. The DJB2 algorithm can be called using the HashString SDK function. This function takes a string value and returns a 16-bit hash. This is perfect for creating hash tables like the one described above. MD5 hashes can be created by using the MD5CreateDigest function or by using a MD5 Legato object obtained with the MD5NewDigestObject function. The former is a fast way to hash a file or string while the latter can build a hash as data becomes available (such as reading from a file in a loop). Although the MD5 algorithm is a cryptographic hash, it is considered to be unsafe for cryptographic purposes due to several vulnerabilities that make MD5 hashes easy to forge. That being said, it is still great for verifying downloads or other non-cryptographic data. For example, one of our other bloggers and developers, Steve Horowitz, used it in a previous blog post to detect if two XBRL contexts were the same.

What if you wanted to use a newer hash that was still considered to be secure for cryptographic use, such as the Secure Hash Algorithms? Why not write it in Legato? Since you can include other script files in your scripts, you will be able to add this hash script into any other projects that need it. For this blog, I decided to write an implementation of SHA-3. Unlike its predecessors SHA-2 and SHA-1, SHA-3 it uses a “sponge”-like design to allow for any amount of data input to be “absorbed” by the sponge. Likewise any amount of data can be “squeezed” from the sponge. This script relies heavily on bitwise operators so I will have a brief recap here:

Now for the script:

#define SHA3_224_HASH_SIZE 28
#define SHA3_256_HASH_SIZE 32
#define SHA3_384_HASH_SIZE 48
#define SHA3_512_HASH_SIZE 64
#define SHA3_MAX_PERM_SIZE 25
#define SHA3_MAX_RATE      24
#define SHA3_MAX_RATE_BYTE 200

#define NUMBEROFROUNDS     24


// Control Data
qword   gbl_hash[SHA3_MAX_PERM_SIZE];
qword   gbl_msg[SHA3_MAX_RATE];
dword   gbl_cnt;
byte    gbl_blk_sz;
boolean gbl_is_final;

// Constants
qword   gbl_round_constants[NUMBEROFROUNDS];
int     gbl_rotate_constants[5][5];

// High level "Public" Functions
string  sha3_512                (string text);
string  sha3_384                (string text);
string  sha3_256                (string text);
string  sha3_224                (string text);

// "Public" Functions
void    sha3_224_init           ();
void    sha3_256_init           ();
void    sha3_384_init           ();
void    sha3_512_init           ();
void    sha3_update             (string msg, int size);
string  sha3_final              ();

// "Private" Functions
void    _sha3_init              (int bits);
void    _theta                  ();
void    _permutation            ();
void    _process_block          ();

// "Private" Data
qword   p_gbl_blk[SHA3_MAX_PERM_SIZE];

// Run SHA3-512
string sha3_512(string text) {
  sha3_512_init();
  sha3_update(text, (-1));
  return sha3_final();
  }

// Run SHA3-384
string sha3_384(string text) {
  sha3_384_init();
  sha3_update(text, (-1));
  return sha3_final();
  }

// Run SHA3-256
string sha3_256(string text) {
  sha3_256_init();
  sha3_update(text, (-1));
  return sha3_final();
  }

// Run SHA3-224
string sha3_224(string text) {
  sha3_224_init();
  sha3_update(text, (-1));
  return sha3_final();
  }


void sha3_224_init() {
    _sha3_init(224);
    }

void sha3_256_init() {
    _sha3_init(256);
    }

void sha3_384_init() {
    _sha3_init(384);
    }

void sha3_512_init() {
    _sha3_init(512);
    }

// Add message to hash
void sha3_update(string msg, int size) {

    int prev_size;
    int block_size;
    int left;
    int read_pos;
    
    prev_size = gbl_cnt;
    block_size = gbl_blk_sz;
    read_pos = 0;
    
    // Assume string if -1 size
    if (size == -1) {
      size = GetStringLength(msg);
      }

    // Check if finalized already
    if (gbl_is_final) {
      return;
      }

    gbl_cnt = ((gbl_cnt + size) % block_size);

    // Fill partial block
    if (gbl_cnt) {
      left = block_size - prev_size;

      // Our data still doesn't fill a block
      if (size < left) {
        BinaryCopySegment(msg, gbl_msg, read_pos, prev_size, size);
        return;
        }

      // Process it
      BinaryCopySegment(msg, gbl_msg, read_pos, prev_size, left);
      p_gbl_blk = gbl_msg;
      _process_block();
      
      read_pos += left;
      size -= left;
      }

    // Fill and Process blocks
    while (size >= block_size) {

      BinaryCopySegment(msg, p_gbl_blk, read_pos, 0, block_size);
      _process_block();

      read_pos += block_size;
      size -= block_size;
      }
    
    // Save any unprocessed data (less than 1 block)
    if (size != 0) {
      BinaryCopySegment(msg, gbl_msg, read_pos, 0, size);
      }
    }

// Finalize Hash
string sha3_final() {

    char  lmsg[SHA3_MAX_RATE_BYTE];  // Same size as gbl_msg
    int   digest_length;
    
    digest_length = 100 - gbl_blk_sz / 2;

    // Has not been finalized?
    if (!gbl_is_final) {
      // Copy Remainder into local variable
      BinaryCopySegment(gbl_msg, lmsg, 0, 0, gbl_cnt);
      // Add Markers
      lmsg[gbl_cnt       ] |= 0x06;
      lmsg[gbl_blk_sz - 1] |= 0x80;

      // Process Final Block
      BinaryCopySegment(lmsg, p_gbl_blk, 0, 0, gbl_blk_sz);
      _process_block();

      // Mark as final
      gbl_is_final = true;
      }
      
    // Get Value
    return HexBufferToString(gbl_hash, digest_length);
    }

//
// Private Functions
//

// Bit shift with rotate
qword _rotate_left(qword val, int n) {
    qword p1, p2, res;
    qword signmask;
    
    signmask = Power(2, n) - 1;
    
    p1 = val << n;
    n = 64 - n;
    p2 = (val >> n) & signmask;
    res = p1 ^ p2;
    return res;
    }

// Initialize for given number of output bits
void _sha3_init(int bits) {
    int         ix;
    int         rate;
    
    // Clear All Control Data
    for (ix = 0; ix < SHA3_MAX_PERM_SIZE; ix++) {
      gbl_hash[ix] = 0;
      }
    for (ix = 0; ix < SHA3_MAX_RATE; ix++) {
      gbl_msg[ix] = 0;
      }
    gbl_cnt = 0;
    gbl_blk_sz = 0;
    gbl_is_final = false;
    
    // Set up
    rate = 1600 - bits * 2;
    gbl_blk_sz = rate / 8;
    if ((rate > 1600) || ((rate % 64) != 0)) {
      AddMessage("Invalid bit size!");
      }
      
    // Set Round Constants
    gbl_round_constants[ 0] = 0x0000000000000001;
    gbl_round_constants[ 1] = 0x0000000000008082;
    gbl_round_constants[ 2] = 0x800000000000808A;
    gbl_round_constants[ 3] = 0x8000000080008000;
    gbl_round_constants[ 4] = 0x000000000000808B;
    gbl_round_constants[ 5] = 0x0000000080000001;
    gbl_round_constants[ 6] = 0x8000000080008081;
    gbl_round_constants[ 7] = 0x8000000000008009;
    gbl_round_constants[ 8] = 0x000000000000008A;
    gbl_round_constants[ 9] = 0x0000000000000088;
    gbl_round_constants[10] = 0x0000000080008009;
    gbl_round_constants[11] = 0x000000008000000A;
    gbl_round_constants[12] = 0x000000008000808B;
    gbl_round_constants[13] = 0x800000000000008B;
    gbl_round_constants[14] = 0x8000000000008089;
    gbl_round_constants[15] = 0x8000000000008003;
    gbl_round_constants[16] = 0x8000000000008002;
    gbl_round_constants[17] = 0x8000000000000080;
    gbl_round_constants[18] = 0x000000000000800A;
    gbl_round_constants[19] = 0x800000008000000A;
    gbl_round_constants[20] = 0x8000000080008081;
    gbl_round_constants[21] = 0x8000000000008080;
    gbl_round_constants[22] = 0x0000000080000001;
    gbl_round_constants[23] = 0x8000000080008008;
    
    // Set Rotate Constants
    gbl_rotate_constants[0][0] =  0;
    gbl_rotate_constants[0][1] = 36;
    gbl_rotate_constants[0][2] =  3;
    gbl_rotate_constants[0][3] = 41;
    gbl_rotate_constants[0][4] = 18;
    gbl_rotate_constants[1][0] =  1;
    gbl_rotate_constants[1][1] = 44;
    gbl_rotate_constants[1][2] = 10;
    gbl_rotate_constants[1][3] = 45;
    gbl_rotate_constants[1][4] =  2;
    gbl_rotate_constants[2][0] = 62;
    gbl_rotate_constants[2][1] =  6;
    gbl_rotate_constants[2][2] = 43;
    gbl_rotate_constants[2][3] = 15;
    gbl_rotate_constants[2][4] = 61;
    gbl_rotate_constants[3][0] = 28;
    gbl_rotate_constants[3][1] = 55;
    gbl_rotate_constants[3][2] = 25;
    gbl_rotate_constants[3][3] = 21;
    gbl_rotate_constants[3][4] = 56;
    gbl_rotate_constants[4][0] = 27;
    gbl_rotate_constants[4][1] = 20;
    gbl_rotate_constants[4][2] = 39;
    gbl_rotate_constants[4][3] =  8;
    gbl_rotate_constants[4][4] = 14;
    
    // Force arrays to size
    p_gbl_blk[SHA3_MAX_PERM_SIZE - 1]     = 0;
    }

// C value
qword _theta_get_c(int i) {
    qword res;
    res  = gbl_hash[i     ];
    res ^= gbl_hash[i +  5];
    res ^= gbl_hash[i + 10];
    res ^= gbl_hash[i + 15];
    res ^= gbl_hash[i + 20];
    return res;
    }
    
// Theta Function
void _theta() {
    qword d[5];
    
    // Compute parity
    d[0] = _rotate_left(_theta_get_c(1), 1) ^ _theta_get_c(4);
    d[1] = _rotate_left(_theta_get_c(2), 1) ^ _theta_get_c(0);
    d[2] = _rotate_left(_theta_get_c(3), 1) ^ _theta_get_c(1);
    d[3] = _rotate_left(_theta_get_c(4), 1) ^ _theta_get_c(2);
    d[4] = _rotate_left(_theta_get_c(0), 1) ^ _theta_get_c(3);
    
    // Column 1
    gbl_hash[ 0] ^= d[0];
    gbl_hash[ 5] ^= d[0];
    gbl_hash[10] ^= d[0];
    gbl_hash[15] ^= d[0];
    gbl_hash[20] ^= d[0];
    
    // Column 2
    gbl_hash[ 1] ^= d[1];
    gbl_hash[ 6] ^= d[1];
    gbl_hash[11] ^= d[1];
    gbl_hash[16] ^= d[1];
    gbl_hash[21] ^= d[1];

    // Column 3
    gbl_hash[ 2] ^= d[2];
    gbl_hash[ 7] ^= d[2];
    gbl_hash[12] ^= d[2];
    gbl_hash[17] ^= d[2];
    gbl_hash[22] ^= d[2];

    // Column 4
    gbl_hash[ 3] ^= d[3];
    gbl_hash[ 8] ^= d[3];
    gbl_hash[13] ^= d[3];
    gbl_hash[18] ^= d[3];
    gbl_hash[23] ^= d[3];

    // Column 5
    gbl_hash[ 4] ^= d[4];
    gbl_hash[ 9] ^= d[4];
    gbl_hash[14] ^= d[4];
    gbl_hash[19] ^= d[4];
    gbl_hash[24] ^= d[4];
    }

void _permutation() {
    qword b[SHA3_MAX_PERM_SIZE];
    int round;
    int x, y;
    int ix1, ix2, ix3, ix4;
    
    for (round = 0; round < NUMBEROFROUNDS; round++) {

      // Run Theta
      _theta();
      
      // rho and pi transformation
      for (x = 0; x < 5; x++) {
        for (y = 0; y < 5; y++) {
          // Get destination position
          ix1 = (2 * x + 3 * y) % 5;
          ix1 = y + (ix1 * 5);
          // Get source position
          ix2 = x + (y * 5);

          b[ix1] = _rotate_left(gbl_hash[ix2], gbl_rotate_constants[x][y]);
          }
        }

      // Run chi
      for (x = 0; x < 5; x++) {
        for (y = 0; y < 5; y++) {
          // Get destination position
          ix1 = x + (y * 5);
          // Get source positions
          ix2 = x + (y * 5);
          ix3 = ((x + 1) % 5) + (y * 5);
          ix4 = ((x + 2) % 5) + (y * 5);

          gbl_hash[ix1] = b[ix2] ^ ((~b[ix3]) & b[ix4]);
          }
        }

      // Run tau
      gbl_hash[0] ^= gbl_round_constants[round];
      }
    }


void _process_block() {

    // Assumes Little Endian Architecture
    gbl_hash[ 0] ^= p_gbl_blk[ 0];
    gbl_hash[ 1] ^= p_gbl_blk[ 1];
    gbl_hash[ 2] ^= p_gbl_blk[ 2];
    gbl_hash[ 3] ^= p_gbl_blk[ 3];
    gbl_hash[ 4] ^= p_gbl_blk[ 4];
    gbl_hash[ 5] ^= p_gbl_blk[ 5];
    gbl_hash[ 6] ^= p_gbl_blk[ 6];
    gbl_hash[ 7] ^= p_gbl_blk[ 7];
    gbl_hash[ 8] ^= p_gbl_blk[ 8];

    // if not sha3-512
    if (gbl_blk_sz > 72) {
      gbl_hash[ 9] ^= p_gbl_blk[ 9];
      gbl_hash[10] ^= p_gbl_blk[10];
      gbl_hash[11] ^= p_gbl_blk[11];
      gbl_hash[12] ^= p_gbl_blk[12];

      // if not sha3-384
      if (gbl_blk_sz > 104) {
        gbl_hash[13] ^= p_gbl_blk[13];
        gbl_hash[14] ^= p_gbl_blk[14];
        gbl_hash[15] ^= p_gbl_blk[15];
        gbl_hash[16] ^= p_gbl_blk[16];

        // if not sha3-256
        if (gbl_blk_sz > 136) {
          gbl_hash[17] ^= p_gbl_blk[17];

          // if not sha3-224 */
          if (gbl_blk_sz > 144) {
            gbl_hash[18] ^= p_gbl_blk[18];
            gbl_hash[19] ^= p_gbl_blk[19];
            gbl_hash[20] ^= p_gbl_blk[20];
            gbl_hash[21] ^= p_gbl_blk[21];
            gbl_hash[22] ^= p_gbl_blk[22];
            gbl_hash[23] ^= p_gbl_blk[23];
            gbl_hash[24] ^= p_gbl_blk[24];
            }
          }
        }
      }

    // Run Permutate
    _permutation();
    }

As usual, let’s start with the define statements. We have a few that are the sizes of the various hashes in bytes (for example, the 512-bit hash is 64 bytes (512 = 8 * 64)). We also have the size of the permutation memory in qwords. In Legato, a qword is an unsigned 64-bit number. So our permutation block is going to be 25 * 64 or 1,600 bits. Next, we have the rate, which is the maximum size we will input into the sponge at one time in qwords. We also have a define for the size of this in bytes to aid with input later on. Lastly, we also have the number of permutation rounds (24) as defined by the SHA-3 specification.

#define SHA3_224_HASH_SIZE 28
#define SHA3_256_HASH_SIZE 32
#define SHA3_384_HASH_SIZE 48
#define SHA3_512_HASH_SIZE 64
#define SHA3_MAX_PERM_SIZE 25
#define SHA3_MAX_RATE      24
#define SHA3_MAX_RATE_BYTE 200

#define NUMBEROFROUNDS     24

Next we have our control data for the hashing functions. These variables begin with “gbl_” to indicate they are global. The gbl_hash is our current hash state, where gbl_msg is any partial message data that has yet to be absorbed by the sponge. The gbl_cnt variable is the number of bytes of data available in gbl_msg. The gbl_blk_sz variable is the size of data we are entering into the sponge at one time and gbl_is_final is a boolean value to indicate whether the hash has been finalized. If gbl_is_final is true, no more data can be added to the sponge. We also have two variables for constants: gbl_round_constants and gbl_rotate_constants. Since Legato does not have static constants, we will initialize these variables during our hash initialization.

// Control Data
qword   gbl_hash[SHA3_MAX_PERM_SIZE];
qword   gbl_msg[SHA3_MAX_RATE];
dword   gbl_cnt;
byte    gbl_blk_sz;
boolean gbl_is_final;

// Constants
qword   gbl_round_constants[NUMBEROFROUNDS];
int     gbl_rotate_constants[5][5];

Now that the global variables are out of the way we can discuss the functions. Our functions are split into three sections. The first section are high-level hashing functions. These are the functions that other scripts will use to create a hash of a string with no fuss. The next section are functions that other scripts can use to create hashes but they must use them in the proper order. They must call an initialization function (like sha3_224_init), then sha3_update, and finally sha3_final. Much like the MD5 object discussed above, these offer more flexibility since data can be added to the hash as it becomes available. After that we have “private” functions. These are not meant to be called by other Legato scripts, although Legato does apply any such limitations. These functions are internal to the hashing algorithm. We also have private global data that is used to transfer data among the functions. Legato passes copies of variables to functions, so if we want our internal functions to edit our variables we need to use global variables or serialize/unserialize arrays. Global variables are significantly easier to work with and perform better.

// High level "Public" Functions
string  sha3_512                (string text);
string  sha3_384                (string text);
string  sha3_256                (string text);
string  sha3_224                (string text);

// "Public" Functions
void    sha3_224_init           ();
void    sha3_256_init           ();
void    sha3_384_init           ();
void    sha3_512_init           ();
void    sha3_update             (string msg, int size);
string  sha3_final              ();

// "Private" Functions
void    _sha3_init              (int bits);
void    _theta                  ();
void    _permutation            ();
void    _process_block          ();

// "Private" Data
qword   p_gbl_blk[SHA3_MAX_PERM_SIZE];

Let’s look at an example of one of our high level functions. The sha_512 function takes a string as input and returns the hash as a string. It simply calls the appropriate initialize (in this case 512). Then it calls the sha3_update function with the passed string and -1 for the size. Finally, this function returns the result of sha3_final. Basically it initializes the hash, updates it, and finalizes it all in one go. The other high level functions are all the same with different initialization functions so I will skip over them.

string sha3_512(string text) {
  sha3_512_init();
  sha3_update(text, (-1));
  return sha3_final();
  }

Next we have the public initialize functions. These are all the same as well because they all call the internal initialize with a specific size. Instead of following the order of the functions in the file, let’s jump to the internal initialize function. This function clears all the global variables and then calculates the block size based on the requested hash size. If the block size is larger than we can handle or not qword aligned, a message box is displayed with the error. Next we set all the global constant variables. The values of these arrays are from the SHA-3 specification. Finally we initialize our private array to force Legato to size them. This last step is not needed since we are using the BinaryCopySegment function later one, but if we don’t do this the arrays never have their used size set. This, in turn, means you cannot view them in the debugger.

void _sha3_init(int bits) {
    int         ix;
    int         rate;
    
    // Clear All Control Data
    for (ix = 0; ix < SHA3_MAX_PERM_SIZE; ix++) {
      gbl_hash[ix] = 0;
      }
    for (ix = 0; ix < SHA3_MAX_RATE; ix++) {
      gbl_msg[ix] = 0;
      }
    gbl_cnt = 0;
    gbl_blk_sz = 0;
    gbl_is_final = false;
    
    // Set up
    rate = 1600 - bits * 2;
    gbl_blk_sz = rate / 8;
    if ((rate > 1600) || ((rate % 64) != 0)) {
      AddMessage("Invalid bit size!");
      }
      
    // Set Round Constants
    gbl_round_constants[ 0] = 0x0000000000000001;
    gbl_round_constants[ 1] = 0x0000000000008082;
    gbl_round_constants[ 2] = 0x800000000000808A;
    gbl_round_constants[ 3] = 0x8000000080008000;
    gbl_round_constants[ 4] = 0x000000000000808B;
    gbl_round_constants[ 5] = 0x0000000080000001;
    gbl_round_constants[ 6] = 0x8000000080008081;
    gbl_round_constants[ 7] = 0x8000000000008009;
    gbl_round_constants[ 8] = 0x000000000000008A;
    gbl_round_constants[ 9] = 0x0000000000000088;
    gbl_round_constants[10] = 0x0000000080008009;
    gbl_round_constants[11] = 0x000000008000000A;
    gbl_round_constants[12] = 0x000000008000808B;
    gbl_round_constants[13] = 0x800000000000008B;
    gbl_round_constants[14] = 0x8000000000008089;
    gbl_round_constants[15] = 0x8000000000008003;
    gbl_round_constants[16] = 0x8000000000008002;
    gbl_round_constants[17] = 0x8000000000000080;
    gbl_round_constants[18] = 0x000000000000800A;
    gbl_round_constants[19] = 0x800000008000000A;
    gbl_round_constants[20] = 0x8000000080008081;
    gbl_round_constants[21] = 0x8000000000008080;
    gbl_round_constants[22] = 0x0000000080000001;
    gbl_round_constants[23] = 0x8000000080008008;
    
    // Set Rotate Constants
    gbl_rotate_constants[0][0] =  0;
    gbl_rotate_constants[0][1] = 36;
    gbl_rotate_constants[0][2] =  3;
    gbl_rotate_constants[0][3] = 41;
    gbl_rotate_constants[0][4] = 18;
    gbl_rotate_constants[1][0] =  1;
    gbl_rotate_constants[1][1] = 44;
    gbl_rotate_constants[1][2] = 10;
    gbl_rotate_constants[1][3] = 45;
    gbl_rotate_constants[1][4] =  2;
    gbl_rotate_constants[2][0] = 62;
    gbl_rotate_constants[2][1] =  6;
    gbl_rotate_constants[2][2] = 43;
    gbl_rotate_constants[2][3] = 15;
    gbl_rotate_constants[2][4] = 61;
    gbl_rotate_constants[3][0] = 28;
    gbl_rotate_constants[3][1] = 55;
    gbl_rotate_constants[3][2] = 25;
    gbl_rotate_constants[3][3] = 21;
    gbl_rotate_constants[3][4] = 56;
    gbl_rotate_constants[4][0] = 27;
    gbl_rotate_constants[4][1] = 20;
    gbl_rotate_constants[4][2] = 39;
    gbl_rotate_constants[4][3] =  8;
    gbl_rotate_constants[4][4] = 14;
    
    // Force arrays to size
    p_gbl_blk[SHA3_MAX_PERM_SIZE - 1]     = 0;
    }

Back to our public functions. Let’s dig into the sha3_update function. First, this function takes two input parameters: a string of data (which can be binary) and the size of the string of data. If the size parameter is -1, we will treat msg as a string and use the GetStringLength function to retrieve its size. We also define a few variables. prev_pos is the previous size of gbl_msg. The block_size variable is an integer version of the gbl_blk_sz. The left variable is amount of space left in gbl_msg. And, finally, read_pos is the current position of our data in msg.

We start off by initializing our variables. If we don’t have a size, we get the length of msg as described above. Next we have a check to see if we have already finalized the hash. If so, we need to stop.

void sha3_update(string msg, int size) {

    int prev_size;
    int block_size;
    int left;
    int read_pos;
    
    prev_size = gbl_cnt;
    block_size = gbl_blk_sz;
    read_pos = 0;
    
    // Assume string if -1 size
    if (size == -1) {
      size = GetStringLength(msg);
      }

    // Check if finalized already
    if (gbl_is_final) {
      return;
      }

Now that everything is set up, we set gbl_cnt to the remaining amount of data as if we processed everything. If we will have a partial block, we need to deal with that. We set left to the amount of space left in gbl_msg. If our size is smaller than the space remaining, we copy from msg to gbl_msg using BinaryCopySegment. This function copies the data from one variable to another with offsets. We want to use this instead of copying the contents directly since our message array is an array of 64-bit numbers and our source can be any size. Here our offset for the msg variable is our read_pos, which at this point is 0. Our offset for gbl_msg is prev_size. Then we leave since we “processed” the data by storing it for later until we have a complete block to process. If size was greater than or equal to the space remaining, we copy that amount to gbl_msg and then call _process_block on gbl_msg. That function is the core of the hash, which I will cover in a little bit. After that, we increment our read_pos and decrement our size by the amount of data processed.

    gbl_cnt = ((gbl_cnt + size) % block_size);

    // Fill partial block
    if (gbl_cnt) {
      left = block_size - prev_size;
      if (size < left) {
        BinaryCopySegment(msg, gbl_msg, read_pos, prev_size, size);
        return;
        }

      // Process it
      BinaryCopySegment(msg, gbl_msg, read_pos, prev_size, left);
      p_gbl_blk = gbl_msg;
      _process_block();
      
      read_pos += left;
      size -= left;
      }

Now we can do the main processing loop. While we have a block worth of data, we copy it and call _process_block. Once that’s done, we update the size remaining and our position and move on. When we are done with the main processing loop, we copy any remaining msg into gbl_msg. Remember that gbl_cnt is the amount used in gbl_msg and was set above.

    // Fill and Process blocks
    while (size >= block_size) {

      BinaryCopySegment(msg, p_gbl_blk, read_pos, 0, block_size);
      _process_block();

      read_pos += block_size;
      size -= block_size;
      }
    
    // Save any unprocessed data (less than 1 block)
    if (size != 0) {
      BinaryCopySegment(msg, gbl_msg, read_pos, 0, size);
      }
    }

Before diving into _process_block, I am going to talk about sha3_final since it is very similar to sha3_update. In the sha3_final routine, we first calculate the length of the resulting digest in bytes. Then if we are not already finalized, we copy from gbl_msg to a local variable. Because Legato clears local variables, we can copy only the used portion of gbl_msg and the rest of the resulting variable will be 0. Then we can add a padding marker to the data. The specification says to add a bit to the end of the data and then some to the end of the block. So we edit the lmsg variable directly since it is an array of 1 byte characters. Then we process the block as if it was all data even though it contains padding. You may have also noticed that padding is always added regardless of the data size. This is to avoid vulnerabilities involving data that is similar to padding. After that, we set gbl_is_final to true so no more data can be added. Finally, we use the HexBufferToString function on the gbl_hash variable to get the digest value. This is the “squeeze” step where we take data from the sponge. For this variant this step is simply copying the sponge contents.

// Finalize Hash
string sha3_final() {

    char  lmsg[SHA3_MAX_RATE_BYTE];  // Same size as gbl_msg
    int   digest_length;
    
    digest_length = 100 - gbl_blk_sz / 2;

    // Has not been finalized?
    if (!gbl_is_final) {
      // Copy Remainder into local variable
      BinaryCopySegment(gbl_msg, lmsg, 0, 0, gbl_cnt);
      // Add Markers
      lmsg[gbl_cnt       ] |= 0x06;
      lmsg[gbl_blk_sz - 1] |= 0x80;

      // Process Final Block
      BinaryCopySegment(lmsg, p_gbl_blk, 0, 0, gbl_blk_sz);
      _process_block();

      // Mark as final
      gbl_is_final = true;
      }
      
    // Get Value
    return HexBufferToString(gbl_hash, digest_length);
    }

This covers the “public” facing functions of the algorithm. With that under our belt, we can dig into the hashing process itself. We can start with a helper function that will rotate a qword. If you look at the bit shifting operators above, they will either 0 fill or sign extend the qword value. So if we want shifted bits to cycle back to the other side, we need to write this functionality ourselves. Consider the example 1001 << 1 = 0010. If we wanted to rotate that, the result should be rotate_left(1001, 1) = 0011. To accomplish this programmatically, all we need to do is shift the value the correct amount in one direction and then shift the value the inverse amount in the other direction and XOR the results together. Since Legato sign extends shifting operations, we will also need to remove the extended sign.

// Bit shift with rotate
qword _rotate_left(qword val, int n) {
    qword p1, p2, res;
    qword signmask;
    
    signmask = Power(2, n) - 1;
    
    p1 = val << n;
    n = 64 - n;
    p2 = (val >> n) & signmask;
    res = p1 ^ p2;
    return res;
    }

With the helper function out of the way, let’s talk about the _process_block function. The majority of the function is using XOR to “absorb” the incoming data into our hash. After it is absorbed, we “randomize” it using a _permutation function. This permutation function is pseudo random, which is to say it appears random but has consistent output given consistent input. This function assumes we are running on a little endian processor, which stores numbers with the least significant bit first. Since that includes all platforms that Legato runs on, it is a safe assumption.

void _process_block() {

    // Assumes Little Endian Architecture
    gbl_hash[ 0] ^= p_gbl_blk[ 0];
    gbl_hash[ 1] ^= p_gbl_blk[ 1];
    gbl_hash[ 2] ^= p_gbl_blk[ 2];
    gbl_hash[ 3] ^= p_gbl_blk[ 3];
    gbl_hash[ 4] ^= p_gbl_blk[ 4];
    gbl_hash[ 5] ^= p_gbl_blk[ 5];
    gbl_hash[ 6] ^= p_gbl_blk[ 6];
    gbl_hash[ 7] ^= p_gbl_blk[ 7];
    gbl_hash[ 8] ^= p_gbl_blk[ 8];

    // if not sha3-512
    if (gbl_blk_sz > 72) {
      gbl_hash[ 9] ^= p_gbl_blk[ 9];
      gbl_hash[10] ^= p_gbl_blk[10];
      gbl_hash[11] ^= p_gbl_blk[11];
      gbl_hash[12] ^= p_gbl_blk[12];

      // if not sha3-384
      if (gbl_blk_sz > 104) {
        gbl_hash[13] ^= p_gbl_blk[13];
        gbl_hash[14] ^= p_gbl_blk[14];
        gbl_hash[15] ^= p_gbl_blk[15];
        gbl_hash[16] ^= p_gbl_blk[16];

        // if not sha3-256
        if (gbl_blk_sz > 136) {
          gbl_hash[17] ^= p_gbl_blk[17];

          // if not sha3-224
          if (gbl_blk_sz > 144) {
            gbl_hash[18] ^= p_gbl_blk[18];
            gbl_hash[19] ^= p_gbl_blk[19];
            gbl_hash[20] ^= p_gbl_blk[20];
            gbl_hash[21] ^= p_gbl_blk[21];
            gbl_hash[22] ^= p_gbl_blk[22];
            gbl_hash[23] ^= p_gbl_blk[23];
            gbl_hash[24] ^= p_gbl_blk[24];
            }
          }
        }
      }

    // Run Permutate
    _permutation();
    }

The block processing function was pretty straight forward so let’s look at the _permutation function. We are going to start with a loop that iterates for each round, and during each round we are going to perform several steps. We start with the θ theta step, then the ρ rho and π pi steps, then the χ chi step and finally the τ tau step. At the end of this blog there is a link to the specification if you wish to learn more about these steps.

void _permutation() {
    qword b[SHA3_MAX_PERM_SIZE];
    int round;
    int x, y;
    int ix1, ix2, ix3, ix4;
    
    for (round = 0; round < NUMBEROFROUNDS; round++) {

      // Run Theta
      _theta();
      
...

      }
    }

If you are curious, the SHA-3 specification is designed to run on a 5x5 matrix of 64-bit integers, so in our representation we have a single array that is 25 64-bit integers. What this means is a lot of steps will be referencing array positions in blocks of five (0-4, 5-9, etc.). This function has all the steps except the theta step, which is done as another function. So let’s start by looking at the theta step and then come back to the _permutation function.

The theta step is defined as:

  C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4],   for x in 0…4
  D[x] = C[x-1] xor rot(C[x+1],1),                             for x in 0…4
  A[x,y] = A[x,y] xor D[x],                           for (x,y) in (0…4,0…4)

A is the hash matrix. In order to accomplish this step, we will create an array to represent D and a function that calculates the value of C. The function for C looks like this.

qword _theta_get_c(int i) {
    qword res;
    res  = gbl_hash[i     ];
    res ^= gbl_hash[i +  5];
    res ^= gbl_hash[i + 10];
    res ^= gbl_hash[i + 15];
    res ^= gbl_hash[i + 20];
    return res;
    }

The value of C[x] is all the “row” values XOR’ed together. Since we are using an array instead of a matrix, 0, 5, 10, 15 and 20 are the beginnings of each “row” of data. Now that we have the C calculation, we should look at the theta function itself. We calculate D using _rotate_left and our _theta_get_c function, and then we apply the result to our array.

void _theta() {
    qword d[5];
    
    // Compute parity
    d[0] = _rotate_left(_theta_get_c(1), 1) ^ _theta_get_c(4);
    d[1] = _rotate_left(_theta_get_c(2), 1) ^ _theta_get_c(0);
    d[2] = _rotate_left(_theta_get_c(3), 1) ^ _theta_get_c(1);
    d[3] = _rotate_left(_theta_get_c(4), 1) ^ _theta_get_c(2);
    d[4] = _rotate_left(_theta_get_c(0), 1) ^ _theta_get_c(3);
    
    // Column 1
    gbl_hash[ 0] ^= d[0];
    gbl_hash[ 5] ^= d[0];
    gbl_hash[10] ^= d[0];
    gbl_hash[15] ^= d[0];
    gbl_hash[20] ^= d[0];
    
    // Column 2
    gbl_hash[ 1] ^= d[1];
    gbl_hash[ 6] ^= d[1];
    gbl_hash[11] ^= d[1];
    gbl_hash[16] ^= d[1];
    gbl_hash[21] ^= d[1];

    // Column 3
    gbl_hash[ 2] ^= d[2];
    gbl_hash[ 7] ^= d[2];
    gbl_hash[12] ^= d[2];
    gbl_hash[17] ^= d[2];
    gbl_hash[22] ^= d[2];

    // Column 4
    gbl_hash[ 3] ^= d[3];
    gbl_hash[ 8] ^= d[3];
    gbl_hash[13] ^= d[3];
    gbl_hash[18] ^= d[3];
    gbl_hash[23] ^= d[3];

    // Column 5
    gbl_hash[ 4] ^= d[4];
    gbl_hash[ 9] ^= d[4];
    gbl_hash[14] ^= d[4];
    gbl_hash[19] ^= d[4];
    gbl_hash[24] ^= d[4];
    }

Once again, remember we are using an array and not a matrix so the steps of theta use individual positions for the five columns of data. Now let’s look at rho and pi. Note that all of this code is back in the _permutation function.

The rho and pi step is defined as:

  B[y,2*x+3*y] = rot(A[x,y], r[x,y]),                 for (x,y) in (0…4,0…4)

So we need to have an array B to store our rotation results. The r matrix is simply gbl_rotate_constants. Also, if you look at the subscripts for the matrix, they can exceed 0-4. However, the specification says to use modulo 5 on all matrix indices. So our code for this step is going to have nested for loops for x and y. We will calculate the positions in our array and then run the step.

      // rho and pi transformation
      for (x = 0; x < 5; x++) {
        for (y = 0; y < 5; y++) {
          // Get destination position
          ix1 = (2 * x + 3 * y) % 5;
          ix1 = y + (ix1 * 5);
          // Get source position
          ix2 = x + (y * 5);

          b[ix1] = _rotate_left(gbl_hash[ix2], gbl_rotate_constants[x][y]);
          }
        }

You can see our actual code closely resembles the pseudocode for the step. Now that rho and pi are done we can do the chi step. The chi step is defined as:

  A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]),  for (x,y) in (0…4,0…4)

Once again, our matrix indices could go out of range so we will need modulus to correct that. We will use the value of the b array created by rho and pi to update our main hash array. As you can probably predict, this will also involve for loops for x and y and position calculations.

      // Run chi
      for (x = 0; x < 5; x++) {
        for (y = 0; y < 5; y++) {
          // Get destination position
          ix1 = x + (y * 5);
          // Get source positions
          ix2 = x + (y * 5);
          ix3 = ((x + 1) % 5) + (y * 5);
          ix4 = ((x + 2) % 5) + (y * 5);

          gbl_hash[ix1] = b[ix2] ^ ((~b[ix3]) & b[ix4]);
          }
        }

The positions are all calculated at once to simplify the code since the position calculations are a little more complicated for our array set up. Now we can move on to the easiest step, tau. The tau step is defined as:

  A[0,0] = A[0,0] xor RC

The RC variable is the value of the round constant for this round. So it’s easy to see this step will result in a single line of code as follows:

      // Run tau
      gbl_hash[0] ^= gbl_round_constants[round];

Now we are done with a round. The complete _permutation function looks like this:

void _permutation() {
    qword b[SHA3_MAX_PERM_SIZE];
    int round;
    int x, y;
    int ix1, ix2, ix3, ix4;
    
    for (round = 0; round < NUMBEROFROUNDS; round++) {

      // Run Theta
      _theta();
      
      // rho and pi transformation
      for (x = 0; x < 5; x++) {
        for (y = 0; y < 5; y++) {
          // Get destination position
          ix1 = (2 * x + 3 * y) % 5;
          ix1 = y + (ix1 * 5);
          // Get source position
          ix2 = x + (y * 5);

          b[ix1] = _rotate_left(gbl_hash[ix2], gbl_rotate_constants[x][y]);
          }
        }

      // Run chi
      for (x = 0; x < 5; x++) {
        for (y = 0; y < 5; y++) {
          // Get destination position
          ix1 = x + (y * 5);
          // Get source positions
          ix2 = x + (y * 5);
          ix3 = ((x + 1) % 5) + (y * 5);
          ix4 = ((x + 2) % 5) + (y * 5);

          gbl_hash[ix1] = b[ix2] ^ ((~b[ix3]) & b[ix4]);
          }
        }

      // Run tau
      gbl_hash[0] ^= gbl_round_constants[round];
      }
    }

Now for the good stuff. To use this library, all you need to do is save it as a Legato script file. Then you can include it in another Legato script and hash away. Here is an example LS file that shows the empty hash values as well as how changing a single character changes the entire hash value.

#include "sha3.ls"

void main() {
  AddMessage("SHA3-224(\"\")");
  AddMessage( sha3_224(""));
  AddMessage("SHA3-256(\"\")");
  AddMessage( sha3_256(""));
  AddMessage("SHA3-384(\"\")");
  AddMessage( sha3_384(""));
  AddMessage("SHA3-512(\"\")");
  AddMessage( sha3_512(""));

  AddMessage("");
  AddMessage("SHA3-224(\"Test\")");
  AddMessage( sha3_224("Test"));
  AddMessage("SHA3-224(\"test\")");
  AddMessage( sha3_224("test"));
  }

And this is the output:

SHA3-224("")
6B4E03423667DBB73B6E15454F0EB1ABD4597F9A1B078E3F5B5A6BC7
SHA3-256("")
A7FFC6F8BF1ED76651C14756A061D662F580FF4DE43B49FA82D80A4B80F8434A
SHA3-384("")
0C63A75B845E4F7D01107D852E4C2485C51A50AAAA94FC61995E71BBEE983A2AC3713831264ADB47FB6BD1E058D5F004
SHA3-512("")
A69F73CCA23A9AC5C8B567DC185A756E97C982164FE25859E0D1DCC1475C80A615B2123AF1F5F94C11E3E9402C3AC558F500199D95B6D3E301758586281DCD26

SHA3-224("Test")
D40CC4F9630F21EEF0B185BDD6A51EAB1775C1CD6AE458066ECAF046
SHA3-224("test")
3797BF0AFBBFCA4A7BBBA7602A2B552746876517A7F9B7CE2DB0AE7B

Because the algorithm’s output is uniform the hashes of “Test” and “test” are radically different. You can see with a little bit of effort you can program almost anything in Legato, including hashing algorithms that rely heavily on bitwise operations. Likewise, you can use hashing algorithms to add data integrity checks, simplify storage, or to compare unusual data sets. With Legato, anything is possible.

David Theis has been developing software for Windows operating systems for over fifteen years. He has a Bachelor of Sciences in Computer Science from the Rochester Institute of Technology and co-founded Novaworks in 2006. He is the Vice President of Development and is one of the primary developers of GoFiler, a financial reporting software package designed to create and file EDGAR XML, HTML, and XBRL documents to the U.S. Securities and Exchange Commission.

Additional Resources

Novaworks’ Legato Resources

Legato Script Developers LinkedIn Group

Primer: An Introduction to Legato

Keccak Specifications Summary

SHA-3 on Wikipedia

MD5 on Wikipedia

Cyclic redundancy check (CRC) on Wikipedia