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 chrisveness commented Apr 3, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment