Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
32-bit version of SHA-3 (Keccak) algorithm using bit-interleaving
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* SHA-3 (FIPS 202) ‘Keccak’ reference implementation in JavaScript (c) Chris Veness 2016-2017 */
/* MIT Licence */
/* www.movable-type.co.uk/scripts/sha3.html */
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
'use strict';
/**
* SHA-3 (FIPS 202) ‘Keccak’ hash functions.
*
* This is an annotated reference implementation intended to aid understanding of the algorithm.
* While it is fully tested, it is not at all optimised and is not recommended for production use.
*
* See keccak.noekeon.org/Keccak-reference-3.0.pdf
* nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf
*/
class Sha3 {
/*
* Keccak-f[b] permutations:
* - ℓ: 0 1 2 3 4 5 6
* - w: 1 2 4 8 16 32 64 (2ˡ)
* - b: 25 50 100 200 400 800 1600 (25 × 2ˡ)
* SHA-3 specifies Keccak-f[1600] only, hence ℓ=6, w=64, b=1600.
*/
/**
* Generates 224-bit SHA-3 / Keccak hash of message.
*
* @param {string} message - String to be hashed (Unicode-safe).
* @param {Object} options - padding: sha-3 / keccak; msgFormat: string / hex; outFormat: hex / hex-b / hex-w.
* @returns {string} Hash as hex-encoded string.
*/
static hash224(message, options) {
return Sha3.keccak1600(1152, 448, message, options);
}
/**
* Generates 256-bit SHA-3 / Keccak hash of message.
*
* @param {string} message - String to be hashed (Unicode-safe).
* @param {Object} options - padding: sha-3 / keccak; msgFormat: string / hex; outFormat: hex / hex-b / hex-w.
* @returns {string} Hash as hex-encoded string.
*/
static hash256(message, options) {
return Sha3.keccak1600(1088, 512, message, options);
}
/**
* Generates 384-bit SHA-3 / Keccak hash of message.
*
* @param {string} message - String to be hashed (Unicode-safe).
* @param {Object} options - padding: sha-3 / keccak; msgFormat: string / hex; outFormat: hex / hex-b / hex-w.
* @returns {string} Hash as hex-encoded string.
*/
static hash384(message, options) {
return Sha3.keccak1600(832, 768, message, options);
}
/**
* Generates 512-bit SHA-3 / Keccak hash of message.
*
* @param {string} message - String to be hashed (Unicode-safe).
* @param {Object} options - padding: sha-3 / keccak; msgFormat: string / hex; outFormat: hex / hex-b / hex-w.
* @returns {string} Hash as hex-encoded string.
*/
static hash512(message, options) {
return Sha3.keccak1600(576, 1024, message, options);
}
/**
* Generates SHA-3 / Keccak hash of message M.
*
* @param {number} r - Bitrate 'r' (b−c)
* @param {number} c - Capacity 'c' (b−r), md length × 2
* @param {string} M - Message
* @param {Object} options - padding: sha-3 / keccak; msgFormat: string / hex; outFormat: hex / hex-b / hex-w.
* @returns {string} Hash as hex-encoded string.
*
* @private
*/
static keccak1600(r, c, M, options) {
const defaults = { padding: 'sha-3', msgFormat: 'string', outFormat: 'hex' };
const opt = Object.assign(defaults, options);
const l = c / 2; // message digest output length in bits
let msg = null;
switch (opt.msgFormat) {
default: // convert string to UTF-8 to ensure all characters fit within single byte
case 'string': msg = utf8Encode(M); break;
case 'hex-bytes': msg = hexBytesToString(M); break; // mostly for NIST test vectors
}
/**
* Keccak state is a 5 × 5 x w array of bits (w=64 for keccak-f[1600] / SHA-3).
*
* Here, it is implemented as a 5 × 5 × 2 array of 32-bit numbers. The first subscript (x)
* defines the sheet, the second (y) defines the plane, together they define a lane which
* comprises two UInt32. Slices, columns, and individual bits are obtained by bit operations
* on the array[2] representing the lane.
*/
const state = [
[ [0,0], [0,0], [0,0], [0,0], [0,0] ],
[ [0,0], [0,0], [0,0], [0,0], [0,0] ],
[ [0,0], [0,0], [0,0], [0,0], [0,0] ],
[ [0,0], [0,0], [0,0], [0,0], [0,0] ],
[ [0,0], [0,0], [0,0], [0,0], [0,0] ],
];
// append padding (for SHA-3 the domain is 01 hence M||0110*1) [FIPS §B.2]
const q = (r/8) - msg.length % (r/8);
if (q == 1) {
msg += String.fromCharCode(opt.padding=='keccak' ? 0x81 : 0x86);
} else {
msg += String.fromCharCode(opt.padding=='keccak' ? 0x01 : 0x06);
msg += String.fromCharCode(0x00).repeat(q-2);
msg += String.fromCharCode(0x80);
}
// absorbing phase: work through input message in blocks of r bits (r/64 Longs, r/8 bytes)
const w = 64; // for keccak-f[1600]
const blocksize = r / w * 8; // block size in bytes (≡ utf-8 characters)
for (let i=0; i<msg.length; i+=blocksize) {
for (let j=0; j<r/w; j++) {
const lo = (msg.charCodeAt(i+j*8+0)<< 0) + (msg.charCodeAt(i+j*8+1)<< 8)
+ (msg.charCodeAt(i+j*8+2)<<16) + (msg.charCodeAt(i+j*8+3)<<24);
const hi = (msg.charCodeAt(i+j*8+4)<< 0) + (msg.charCodeAt(i+j*8+5)<< 8)
+ (msg.charCodeAt(i+j*8+6)<<16) + (msg.charCodeAt(i+j*8+7)<<24);
const x = j % 5;
const y = Math.floor(j / 5);
const w = toInterleaved([ lo, hi ]);
state[x][y][0] = (state[x][y][0] ^ w[0]) >>> 0; // TODO: >>>0?
state[x][y][1] = (state[x][y][1] ^ w[1]) >>> 0;
}
Sha3.keccak_f_1600(state);
}
// squeezing phase: first l bits of state are message digest
// transpose state, concatenate (little-endian) hex values, & truncate to l bits
let md = transpose(state).map(column => column.map(lane => fromInterleaved(lane).map(w32 => hex(w32).match(/.{2}/g).reverse().join('')).join('')).join('')).join('').slice(0, l/4);
function hex(n) { return ('00000000'+n.toString(16)).slice(-8); }
// if required, group message digest into bytes or words
if (opt.outFormat == 'hex-b') md = md.match(/.{2}/g).join(' ');
if (opt.outFormat == 'hex-w') md = md.match(/.{8,16}/g).join(' ');
return md;
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
function toInterleaved(lane) { // convert (64-bit) lane[low,high] to [even,odd]
let even = 0, odd = 0;
for (let i=0; i<64; i++) {
const bit = i<32 ? (lane[0] >> i) & 1 : (lane[1] >> (i-32)) & 1; // TODO: hi/lo?
if (i%2 == 0) even |= bit << (i/2);
if (i%2 == 1) odd |= bit << ((i-1)/2);
}
return [ even, odd ];
}
function fromInterleaved(lane) { // convert (64-bit) lane[even,odd] to [high,low]
let high = 0, low = 0;
for (let i=0; i<64; i++) {
const bit = (i%2 == 0) ? (lane[0] >>> (i/2)) & 1 : (lane[1] >>> ((i-1)/2)) & 1;
if (i < 32) low = (low | bit << i) >>> 0; // TODO: >>>0 needed?
if (i >= 32) high = (high |bit << (i-32)) >>> 0;
}
return [ low>>>0, high>>>0 ];
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
function transpose(array) { // to iterate across y (columns) before x (rows)
return array.map((row, r) => array.map(col => col[r]));
}
function utf8Encode(str) {
try {
return new TextEncoder().encode(str, 'utf-8').reduce((prev, curr) => prev + String.fromCharCode(curr), '');
} catch (e) { // no TextEncoder available?
return unescape(encodeURIComponent(str)); // monsur.hossa.in/2012/07/20/utf-8-in-javascript.html
}
}
function hexBytesToString(hexStr) { // convert string of hex numbers to a string of chars (eg '616263' -> 'abc').
const str = hexStr.replace(' ', ''); // allow space-separated groups
return str=='' ? '' : str.match(/.{2}/g).map(byte => String.fromCharCode(parseInt(byte, 16))).join('');
}
}
/**
* Applies permutation Keccak-f[1600] to state a.
*
* @param {number[][][]} a - State to be permuted (5 × 5 × 2 array of UInt32).
*
* @private
*/
static keccak_f_1600(a) {
const nRounds = 24; // number of rounds nᵣ = 12 + 2ℓ, hence 24 for Keccak-f[1600] [[Keccak §1.2]
/**
* Round constants: output of a maximum-length linear feedback shift register (LFSR) for the
* ι step [Keccak §1.2, §2.3.5], keccak.noekeon.org/specs_summary.html.
*
* RC[iᵣ][0][0][2ʲ−1] = rc[j+7iᵣ] for 0 ≤ j ≤ l
* where
* rc[t] = ( xᵗ mod x⁸ + x⁶ + x⁵ + x⁴ + 1 ) mod x in GF(2)[x].
*/
const RC = [ // TODO: interleaved? word ordering? each word-pair is [even,odd]?
[ 0x00000001, 0x00000000 ], [ 0x00000000, 0x00000089 ], [ 0x00000000, 0x8000008B ],
[ 0x00000000, 0x80008080 ], [ 0x00000001, 0x0000008B ], [ 0x00000001, 0x00008000 ],
[ 0x00000001, 0x80008088 ], [ 0x00000001, 0x80000082 ], [ 0x00000000, 0x0000000B ],
[ 0x00000000, 0x0000000A ], [ 0x00000001, 0x00008082 ], [ 0x00000000, 0x00008003 ],
[ 0x00000001, 0x0000808B ], [ 0x00000001, 0x8000000B ], [ 0x00000001, 0x8000008A ],
[ 0x00000001, 0x80000081 ], [ 0x00000000, 0x80000081 ], [ 0x00000000, 0x80000008 ],
[ 0x00000000, 0x00000083 ], [ 0x00000000, 0x80008003 ], [ 0x00000001, 0x80008088 ],
[ 0x00000000, 0x80000088 ], [ 0x00000001, 0x00008000 ], [ 0x00000000, 0x80008082 ],
];
// Keccak-f permutations
for (let r=0; r<nRounds; r++) {
// apply step mappings θ, ρ, π, χ, ι to the state 'a'
//console.log('round', r); debug5x5(a);
// θ [Keccak §2.3.2]
const C = [ [0,0], [0,0], [0,0], [0,0], [0,0] ]; // intermediate sub-states
const D = [ [0,0], [0,0], [0,0], [0,0], [0,0] ];
for (let x=0; x<5; x++) {
for (let y=0; y<5; y++) {
C[x][0] = (C[x][0] ^ a[x][y][0]) >>> 0;
C[x][1] = (C[x][1] ^ a[x][y][1]) >>> 0;
}
}
for (let x=0; x<5; x++) {
// D[x] = C[x−1] ⊕ ROT(C[x+1], 1)
D[x][0] = (C[(x+4)%5][0] ^ ROT(C[(x+1)%5], 1)[0]) >>> 0;
D[x][1] = (C[(x+4)%5][1] ^ ROT(C[(x+1)%5], 1)[1]) >>> 0;
}
for (let x=0; x<5; x++) {
for (let y=0; y<5; y++) {
a[x][y][0] = (a[x][y][0] ^ D[x][0]) >>> 0;
a[x][y][1] = (a[x][y][1] ^ D[x][1]) >>> 0;
}
}
//console.log('round', r, 'after θ'); debug5x5(a);
// ρ + π [Keccak §2.3.4]
let [ x, y ] = [ 1, 0 ];
let current = a[x][y].slice(0); // Array.slice(0) clones the array
for (let t=0; t<24; t++) {
const [ X, Y ] = [ y, (2*x + 3*y) % 5 ];
const tmp = a[X][Y].slice(0);
a[X][Y] = ROT(current, ((t+1)*(t+2)/2) % 64);
//console.log('ρπ', x, y, current, ((t+1)*(t+2)/2) % 64, X, Y, a[X][Y])
current = tmp;
[ x, y ] = [ X, Y ];
}
// note by folding the π step into the ρ step, it is only necessary to cache the current
// lane; with π looping around x & y, it would be necessary to take a copy of the full
// state for the A[X,Y] = a[x,y] operation
//console.log('round', r, 'after ρπ'); debug5x5(a)
// χ [Keccak §2.3.1]
for (let y=0; y<5; y++) {
const C = [ [0,0], [0,0], [0,0], [0,0], [0,0] ]; // take a copy of the plane
for (let x=0; x<5; x++) {
C[x][0] = (a[x][y][0] ^ ((~a[(x+1)%5][y][0]) & a[(x+2)%5][y][0])) >>> 0;
C[x][1] = (a[x][y][1] ^ ((~a[(x+1)%5][y][1]) & a[(x+2)%5][y][1])) >>> 0;
}
for (let x=0; x<5; x++) {
a[x][y][0] = C[x][0];
a[x][y][1] = C[x][1];
}
}
//console.log('round', r, 'after χ'); debug5x5(a);
// ι [Keccak §2.3.5]
//console.log(RC[r])
a[0][0][0] = (a[0][0][0] ^ RC[r][0]) >>> 0;
a[0][0][1] = (a[0][0][1] ^ RC[r][1]) >>> 0;
//console.log('round', r, 'after ι'); debug5x5(a);
}
function ROT(a, d) { // rotate-left bit-interleaved lane 'a' by d bits
if (d==0) return a;
if (d==1) return [ (a[1] << 1 ^ a[1] >>> 31) >>> 0, a[0]>>>0 ]; // avoid invalid >>> 32! TODO: >>>0?
//console.log('ROT >', a, '>>', d)
let even=null, odd=null;
if (d%2 == 0) {
//d = d/2;
even = ((a[0] << d/2) ^ (a[0] >>> (32-d/2))) >>> 0;
odd = ((a[1] << d/2) ^ (a[1] >>> (32-d/2))) >>> 0;
} else {
//d = (d+1)/2;
even = ((a[1] << (d+1)/2) ^ (a[1] >>> (32-(d+1)/2))) >>> 0;
odd = ((a[0] << (d-1)/2) ^ (a[0] >>> (32-(d-1)/2))) >>> 0;
}
//console.log('ROT <', [ even, odd ])
return [ even, odd ];
}
function debug5x5i(s) { // debug of state s, interleaved (even/odd) format
const d = s.map((row, r) => s.map(col => col[r].map(w => hex(w)).join(':')).join(' ')).join('\n');
console.log(d);
function hex(n) { return ('00000000'+n.toString(16)).slice(-8); }
}
function debug5x5(s) { // debug of state s, high:low word format
const d = transpose(s).map(row => row.map(w=>fromInterleaved2(w)).map(col => col.map(w => hex(w)).join(':')).join(' ')).join('\n');
console.log(d);
function hex(n) { return ('00000000'+n.toString(16)).slice(-8); }
}
function fromInterleaved2(lane) { // convert (64-bit) lane[even,odd] to [high,low]
let high = 0, low = 0;
for (let i=0; i<64; i++) {
const bit = (i%2 == 0) ? (lane[0] >>> (i/2)) & 1 : (lane[1] >>> ((i-1)/2)) & 1;
if (i < 32) low = (low | bit << i) >>> 0; // TODO: >>>0 needed?
if (i >= 32) high = (high |bit << (i-32)) >>> 0;
}
return [ low>>>0, high>>>0 ];
}
function transpose(array) { // TODO: why?
return array.map((row, r) => array.map(col => col[r]));
}
}
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
if (typeof module != 'undefined' && module.exports) module.exports = Sha3; // ≡ export default Sha3
@chrisveness

This comment has been minimized.

Copy link
Owner Author

chrisveness commented Apr 3, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.