This week we are going to discuss hashing. Simply put, a hashing function takes arbitrary sized data and maps it to fixed size in a deterministic manner. Therefore, when given the same input, the same result is generated. Ideally, a hash function would be 1-1, as in for every input a unique output is given. This is also known as an injective function. In reality, though, that’s not possible since the amount of data being input can be many times larger than the output. So instead hashing algorithms aim to be uniform, which is to say they use the entire output space equally. This means that the chances of two inputs generating the same hash are lower given the size of the output hash.
Friday, March 23. 2018
LDC #77: Hash It Out
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:
Name | Operator | Description | Example (binary) |
---|---|---|---|
OR | | | The combination of bits for A OR for B. Where A or B has a 1, the resulting bit is a 1; otherwise, it is a 0. | 0010 | 0001 = 0011 |
AND | & | The combination of bits for A AND for B. Where A and B are both 1, the resulting bit is a 1; otherwise, it is a 0. | 0010 & 0011 = 0010 |
NOT | ~ | The complement of A. All 0s become 1s and 1s become 0s. | ~0010 = 1101 |
XOR | ^ | The combination of bits for A ONLY IF DIFFERENT than B. The resulting bits are 1 where A and B are different and 0 where they are the same. | 0101 ^ 0011 = 0110 |
Right Shift | >> | Bits are shifted to the right. The sign bit is extended in Legato. | 1001 >> 1 = 1100 0100 >> 2 = 0001 |
Left Shift | >> | Bits are shifted to the left and 0s are inserted. | 1001 << 1 = 0010 0001 << 2 = 0100 |
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
Legato Script Developers LinkedIn Group
Primer: An Introduction to Legato
Cyclic redundancy check (CRC) on Wikipedia
Quicksearch
Categories
Calendar
October '24 | ||||||
---|---|---|---|---|---|---|
Mo | Tu | We | Th | Fr | Sa | Su |
Tuesday, October 15. 2024 | ||||||
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |