/*
** Copyright (c) 2017 D. Richard Hipp
**
** This program is free software; you can redistribute it and/or
** modify it under the terms of the Simplified BSD License (also
** known as the "2-Clause License" or "FreeBSD License".)
**
** This program is distributed in the hope that it will be useful,
** but without any warranty; without even the implied warranty of
** merchantability or fitness for a particular purpose.
**
** Author contact information:
** drh@hwaci.com
** http://www.hwaci.com/drh/
**
*******************************************************************************
**
** This file contains an implementation of SHA3 (Keccak) hashing.
*/
#include "config.h"
#include "sha3.h"
/*
** Macros to determine whether the machine is big or little endian,
** and whether or not that determination is run-time or compile-time.
**
** For best performance, an attempt is made to guess at the byte-order
** using C-preprocessor macros. If that is unsuccessful, or if
** -DSHA3_BYTEORDER=0 is set, then byte-order is determined
** at run-time.
*/
#ifndef SHA3_BYTEORDER
# if defined(i386) || defined(__i386__) || defined(_M_IX86) || \
defined(__x86_64) || defined(__x86_64__) || defined(_M_X64) || \
defined(_M_AMD64) || defined(_M_ARM) || defined(__x86) || \
defined(__arm__)
# define SHA3_BYTEORDER 1234
# elif defined(sparc) || defined(__ppc__)
# define SHA3_BYTEORDER 4321
# else
# define SHA3_BYTEORDER 0
# endif
#endif
/*
** State structure for a SHA3 hash in progress
*/
typedef struct SHA3Context SHA3Context;
struct SHA3Context {
union {
u64 s[25]; /* Keccak state. 5x5 lines of 64 bits each */
unsigned char x[1600]; /* ... or 1600 bytes */
} u;
unsigned nRate; /* Bytes of input accepted per Keccak iteration */
unsigned nLoaded; /* Input bytes loaded into u.x[] so far this cycle */
unsigned ixMask; /* Insert next input into u.x[nLoaded^ixMask]. */
};
/*
** A single step of the Keccak mixing function for a 1600-bit state
*/
static void KeccakF1600Step(SHA3Context *p){
int i;
u64 B0, B1, B2, B3, B4;
u64 C0, C1, C2, C3, C4;
u64 D0, D1, D2, D3, D4;
static const u64 RC[] = {
0x0000000000000001ULL, 0x0000000000008082ULL,
0x800000000000808aULL, 0x8000000080008000ULL,
0x000000000000808bULL, 0x0000000080000001ULL,
0x8000000080008081ULL, 0x8000000000008009ULL,
0x000000000000008aULL, 0x0000000000000088ULL,
0x0000000080008009ULL, 0x000000008000000aULL,
0x000000008000808bULL, 0x800000000000008bULL,
0x8000000000008089ULL, 0x8000000000008003ULL,
0x8000000000008002ULL, 0x8000000000000080ULL,
0x000000000000800aULL, 0x800000008000000aULL,
0x8000000080008081ULL, 0x8000000000008080ULL,
0x0000000080000001ULL, 0x8000000080008008ULL
};
# define A00 (p->u.s[0])
# define A01 (p->u.s[1])
# define A02 (p->u.s[2])
# define A03 (p->u.s[3])
# define A04 (p->u.s[4])
# define A10 (p->u.s[5])
# define A11 (p->u.s[6])
# define A12 (p->u.s[7])
# define A13 (p->u.s[8])
# define A14 (p->u.s[9])
# define A20 (p->u.s[10])
# define A21 (p->u.s[11])
# define A22 (p->u.s[12])
# define A23 (p->u.s[13])
# define A24 (p->u.s[14])
# define A30 (p->u.s[15])
# define A31 (p->u.s[16])
# define A32 (p->u.s[17])
# define A33 (p->u.s[18])
# define A34 (p->u.s[19])
# define A40 (p->u.s[20])
# define A41 (p->u.s[21])
# define A42 (p->u.s[22])
# define A43 (p->u.s[23])
# define A44 (p->u.s[24])
# define ROL64(a,x) ((a<<x)|(a>>(64-x)))
for(i=0; i<24; i+=4){
C0 = A00^A10^A20^A30^A40;
C1 = A01^A11^A21^A31^A41;
C2 = A02^A12^A22^A32^A42;
C3 = A03^A13^A23^A33^A43;
C4 = A04^A14^A24^A34^A44;
D0 = C4^ROL64(C1, 1);
D1 = C0^ROL64(C2, 1);
D2 = C1^ROL64(C3, 1);
D3 = C2^ROL64(C4, 1);
D4 = C3^ROL64(C0, 1);
B0 = (A00^D0);
B1 = ROL64((A11^D1), 44);
B2 = ROL64((A22^D2), 43);
B3 = ROL64((A33^D3), 21);
B4 = ROL64((A44^D4), 14);
A00 = B0 ^((~B1)& B2 );
A00 ^= RC[i];
A11 = B1 ^((~B2)& B3 );
A22 = B2 ^((~B3)& B4 );
A33 = B3 ^((~B4)& B0 );
A44 = B4 ^((~B0)& B1 );
B2 = ROL64((A20^D0), 3);
B3 = ROL64((A31^D1), 45);
B4 = ROL64((A42^D2), 61);
B0 = ROL64((A03^D3), 28);
B1 = ROL64((A14^D4), 20);
A20 = B0 ^((~B1)& B2 );
A31 = B1 ^((~B2)& B3 );
A42 = B2 ^((~B3)& B4 );
A03 = B3 ^((~B4)& B0 );
A14 = B4 ^((~B0)& B1 );
B4 = ROL64((A40^D0), 18);
B0 = ROL64((A01^D1), 1);
B1 = ROL64((A12^D2), 6);
B2 = ROL64((A23^D3), 25);
B3 = ROL64((A34^D4), 8);
A40 = B0 ^((~B1)& B2 );
A01 = B1 ^((~B2)& B3 );
A12 = B2 ^((~B3)& B4 );
A23 = B3 ^((~B4)& B0 );
A34 = B4 ^((~B0)& B1 );
B1 = ROL64((A10^D0), 36);
B2 = ROL64((A21^D1), 10);
B3 = ROL64((A32^D2), 15);
B4 = ROL64((A43^D3), 56);
B0 = ROL64((A04^D4), 27);
A10 = B0 ^((~B1)& B2 );
A21 = B1 ^((~B2)& B3 );
A32 = B2 ^((~B3)& B4 );
A43 = B3 ^((~B4)& B0 );
A04 = B4 ^((~B0)& B1 );
B3 = ROL64((A30^D0), 41);
B4 = ROL64((A41^D1), 2);
B0 = ROL64((A02^D2), 62);
B1 = ROL64((A13^D3), 55);
B2 = ROL64((A24^D4), 39);
A30 = B0 ^((~B1)& B2 );
A41 = B1 ^((~B2)& B3 );
A02 = B2 ^((~B3)& B4 );
A13 = B3 ^((~B4)& B0 );
A24 = B4 ^((~B0)& B1 );
C0 = A00^A20^A40^A10^A30;
C1 = A11^A31^A01^A21^A41;
C2 = A22^A42^A12^A32^A02;
C3 = A33^A03^A23^A43^A13;
C4 = A44^A14^A34^A04^A24;
D0 = C4^ROL64(C1, 1);
D1 = C0^ROL64(C2, 1);
D2 = C1^ROL64(C3, 1);
D3 = C2^ROL64(C4, 1);
D4 = C3^ROL64(C0, 1);
B0 = (A00^D0);
B1 = ROL64((A31^D1), 44);
B2 = ROL64((A12^D2), 43);
B3 = ROL64((A43^D3), 21);
B4 = ROL64((A24^D4), 14);
A00 = B0 ^((~B1)& B2 );
A00 ^= RC[i+1];
A31 = B1 ^((~B2)& B3 );
A12 = B2 ^((~B3)& B4 );
A43 = B3 ^((~B4)& B0 );
A24 = B4 ^((~B0)& B1 );
B2 = ROL64((A40^D0), 3);
B3 = ROL64((A21^D1), 45);
B4 = ROL64((A02^D2), 61);
B0 = ROL64((A33^D3), 28);
B1 = ROL64((A14^D4), 20);
A40 = B0 ^((~B1)& B2 );
A21 = B1 ^((~B2)& B3 );
A02 = B2 ^((~B3)& B4 );
A33 = B3 ^((~B4)& B0 );
A14 = B4 ^((~B0)& B1 );
B4 = ROL64((A30^D0), 18);
B0 = ROL64((A11^D1), 1);
B1 = ROL64((A42^D2), 6);
B2 = ROL64((A23^D3), 25);
B3 = ROL64((A04^D4), 8);
A30 = B0 ^((~B1)& B2 );
A11 = B1 ^((~B2)& B3 );
A42 = B2 ^((~B3)& B4 );
A23 = B3 ^((~B4)& B0 );
A04 = B4 ^((~B0)& B1 );
B1 = ROL64((A20^D0), 36);
B2 = ROL64((A01^D1), 10);
B3 = ROL64((A32^D2), 15);
B4 = ROL64((A13^D3), 56);
B0 = ROL64((A44^D4), 27);
A20 = B0 ^((~B1)& B2 );
A01 = B1 ^((~B2)& B3 );
A32 = B2 ^((~B3)& B4 );
A13 = B3 ^((~B4)& B0 );
A44 = B4 ^((~B0)& B1 );
B3 = ROL64((A10^D0), 41);
B4 = ROL64((A41^D1), 2);
B0 = ROL64((A22^D2), 62);
B1 = ROL64((A03^D3), 55);
B2 = ROL64((A34^D4), 39);
A10 = B0 ^((~B1)& B2 );
A41 = B1 ^((~B2)& B3 );
A22 = B2 ^((~B3)& B4 );
A03 = B3 ^((~B4)& B0 );
A34 = B4 ^((~B0)& B1 );
C0 = A00^A40^A30^A20^A10;
C1 = A31^A21^A11^A01^A41;
C2 = A12^A02^A42^A32^A22;
C3 = A43^A33^A23^A13^A03;
C4 = A24^A14^A04^A44^A34;
D0 = C4^ROL64(C1, 1);
D1 = C0^ROL64(C2, 1);
D2 = C1^ROL64(C3, 1);
D3 = C2^ROL64(C4, 1);
D4 = C3^ROL64(C0, 1);
B0 = (A00^D0);
B1 = ROL64((A21^D1), 44);
B2 = ROL64((A42^D2), 43);
B3 = ROL64((A13^D3), 21);
B4 = ROL64((A34^D4), 14);
A00 = B0 ^((~B1)& B2 );
A00 ^= RC[i+2];
A21 = B1 ^((~B2)& B3 );
A42 = B2 ^((~B3)& B4 );
A13 = B3 ^((~B4)& B0 );
A34 = B4 ^((~B0)& B1 );
B2 = ROL64((A30^D0), 3);
B3 = ROL64((A01^D1), 45);
B4 = ROL64((A22^D2), 61);
B0 = ROL64((A43^D3), 28);
B1 = ROL64((A14^D4), 20);
A30 = B0 ^((~B1)& B2 );
A01 = B1 ^((~B2)& B3 );
A22 = B2 ^((~B3)& B4 );
A43 = B3 ^((~B4)& B0 );
A14 = B4 ^((~B0)& B1 );
B4 = ROL64((A10^D0), 18);
B0 = ROL64((A31^D1), 1);
B1 = ROL64((A02^D2), 6);
B2 = ROL64((A23^D3), 25);
B3 = ROL64((A44^D4), 8);
A10 = B0 ^((~B1)& B2 );
A31 = B1 ^((~B2)& B3 );
A02 = B2 ^((~B3)& B4 );
A23 = B3 ^((~B4)& B0 );
A44 = B4 ^((~B0)& B1 );
B1 = ROL64((A40^D0), 36);
B2 = ROL64((A11^D1), 10);
B3 = ROL64((A32^D2), 15);
B4 = ROL64((A03^D3), 56);
B0 = ROL64((A24^D4), 27);
A40 = B0 ^((~B1)& B2 );
A11 = B1 ^((~B2)& B3 );
A32 = B2 ^((~B3)& B4 );
A03 = B3 ^((~B4)& B0 );
A24 = B4 ^((~B0)& B1 );
B3 = ROL64((A20^D0), 41);
B4 = ROL64((A41^D1), 2);
B0 = ROL64((A12^D2), 62);
B1 = ROL64((A33^D3), 55);
B2 = ROL64((A04^D4), 39);
A20 = B0 ^((~B1)& B2 );
A41 = B1 ^((~B2)& B3 );
A12 = B2 ^((~B3)& B4 );
A33 = B3 ^((~B4)& B0 );
A04 = B4 ^((~B0)& B1 );
C0 = A00^A30^A10^A40^A20;
C1 = A21^A01^A31^A11^A41;
C2 = A42^A22^A02^A32^A12;
C3 = A13^A43^A23^A03^A33;
C4 = A34^A14^A44^A24^A04;
D0 = C4^ROL64(C1, 1);
D1 = C0^ROL64(C2, 1);
D2 = C1^ROL64(C3, 1);
D3 = C2^ROL64(C4, 1);
D4 = C3^ROL64(C0, 1);
B0 = (A00^D0);
B1 = ROL64((A01^D1), 44);
B2 = ROL64((A02^D2), 43);
B3 = ROL64((A03^D3), 21);
B4 = ROL64((A04^D4), 14);
A00 = B0 ^((~B1)& B2 );
A00 ^= RC[i+3];
A01 = B1 ^((~B2)& B3 );
A02 = B2 ^((~B3)& B4 );
A03 = B3 ^((~B4)& B0 );
A04 = B4 ^((~B0)& B1 );
B2 = ROL64((A10^D0), 3);
B3 = ROL64((A11^D1), 45);
B4 = ROL64((A12^D2), 61);
B0 = ROL64((A13^D3), 28);
B1 = ROL64((A14^D4), 20);
A10 = B0 ^((~B1)& B2 );
A11 = B1 ^((~B2)& B3 );
A12 = B2 ^((~B3)& B4 );
A13 = B3 ^((~B4)& B0 );
A14 = B4 ^((~B0)& B1 );
B4 = ROL64((A20^D0), 18);
B0 = ROL64((A21^D1), 1);
B1 = ROL64((A22^D2), 6);
B2 = ROL64((A23^D3), 25);
B3 = ROL64((A24^D4), 8);
A20 = B0 ^((~B1)& B2 );
A21 = B1 ^((~B2)& B3 );
A22 = B2 ^((~B3)& B4 );
A23 = B3 ^((~B4)& B0 );
A24 = B4 ^((~B0)& B1 );
B1 = ROL64((A30^D0), 36);
B2 = ROL64((A31^D1), 10);
B3 = ROL64((A32^D2), 15);
B4 = ROL64((A33^D3), 56);
B0 = ROL64((A34^D4), 27);
A30 = B0 ^((~B1)& B2 );
A31 = B1 ^((~B2)& B3 );
A32 = B2 ^((~B3)& B4 );
A33 = B3 ^((~B4)& B0 );
A34 = B4 ^((~B0)& B1 );
B3 = ROL64((A40^D0), 41);
B4 = ROL64((A41^D1), 2);
B0 = ROL64((A42^D2), 62);
B1 = ROL64((A43^D3), 55);
B2 = ROL64((A44^D4), 39);
A40 = B0 ^((~B1)& B2 );
A41 = B1 ^((~B2)& B3 );
A42 = B2 ^((~B3)& B4 );
A43 = B3 ^((~B4)& B0 );
A44 = B4 ^((~B0)& B1 );
}
}
/*
** Initialize a new hash. iSize determines the size of the hash
** in bits and should be one of 224, 256, 384, or 512. Or iSize
** can be zero to use the default hash size of 256 bits.
*/
static void SHA3Init(SHA3Context *p, int iSize){
memset(p, 0, sizeof(*p));
if( iSize>=128 && iSize<=512 ){
p->nRate = (1600 - ((iSize + 31)&~31)*2)/8;
}else{
p->nRate = (1600 - 2*256)/8;
}
#if SHA3_BYTEORDER==1234
/* Known to be little-endian at compile-time. No-op */
#elif SHA3_BYTEORDER==4321
p->ixMask = 7; /* Big-endian */
#else
{
static unsigned int one = 1;
if( 1==*(unsigned char*)&one ){
/* Little endian. No byte swapping. */
p->ixMask = 0;
}else{
/* Big endian. Byte swap. */
p->ixMask = 7;
}
}
#endif
}
/*
** Make consecutive calls to the SHA3Update function to add new content
** to the hash
*/
static void SHA3Update(
SHA3Context *p,
const unsigned char *aData,
unsigned int nData
){
unsigned int i = 0;
#if SHA3_BYTEORDER==1234
if( (p->nLoaded % 8)==0 && (((intptr_t)aData)&7)==0 ){
for(; i+7<nData; i+=8){
p->u.s[p->nLoaded/8] ^= *(u64*)&aData[i];
p->nLoaded += 8;
if( p->nLoaded>=p->nRate ){
KeccakF1600Step(p);
p->nLoaded = 0;
}
}
}
#endif
for(; i<nData; i++){
#if SHA3_BYTEORDER==1234
p->u.x[p->nLoaded] ^= aData[i];
#elif SHA3_BYTEORDER==4321
p->u.x[p->nLoaded^0x07] ^= aData[i];
#else
p->u.x[p->nLoaded^p->ixMask] ^= aData[i];
#endif
p->nLoaded++;
if( p->nLoaded==p->nRate ){
KeccakF1600Step(p);
p->nLoaded = 0;
}
}
}
/*
** After all content has been added, invoke SHA3Final() to compute
** the final hash. The function returns a pointer to the binary
** hash value.
*/
static unsigned char *SHA3Final(SHA3Context *p){
unsigned int i;
if( p->nLoaded==p->nRate-1 ){
const unsigned char c1 = 0x86;
SHA3Update(p, &c1, 1);
}else{
const unsigned char c2 = 0x06;
const unsigned char c3 = 0x80;
SHA3Update(p, &c2, 1);
p->nLoaded = p->nRate - 1;
SHA3Update(p, &c3, 1);
}
for(i=0; i<p->nRate; i++){
p->u.x[i+p->nRate] = p->u.x[i^p->ixMask];
}
return &p->u.x[p->nRate];
}
/*
** Convert a digest into base-16. digest should be declared as
** "unsigned char digest[20]" in the calling function. The SHA3
** digest is stored in the first 20 bytes. zBuf should
** be "char zBuf[41]".
*/
static void DigestToBase16(unsigned char *digest, char *zBuf, int nByte){
static const char zEncode[] = "0123456789abcdef";
int ix;
for(ix=0; ix<nByte; ix++){
*zBuf++ = zEncode[(*digest>>4)&0xf];
*zBuf++ = zEncode[*digest++ & 0xf];
}
*zBuf = '\0';
}
/*
** The state of an incremental SHA3 checksum computation. Only one
** such computation can be underway at a time, of course.
*/
static SHA3Context incrCtx;
static int incrInit = 0;
/*
** Initialize a new global SHA3 hash.
*/
void sha3sum_init(int iSize){
assert( incrInit==0 );
incrInit = iSize;
SHA3Init(&incrCtx, incrInit);
}
/*
** Add more text to the incremental SHA3 checksum.
*/
void sha3sum_step_text(const char *zText, int nBytes){
assert( incrInit );
if( nBytes<=0 ){
if( nBytes==0 ) return;
nBytes = strlen(zText);
}
SHA3Update(&incrCtx, (unsigned char*)zText, nBytes);
}
/*
** Add the content of a blob to the incremental SHA3 checksum.
*/
void sha3sum_step_blob(Blob *p){
assert( incrInit );
SHA3Update(&incrCtx, (unsigned char*)blob_buffer(p), blob_size(p));
}
/*
** Finish the incremental SHA3 checksum. Store the result in blob pOut
** if pOut!=0. Also return a pointer to the result.
**
** This resets the incremental checksum preparing for the next round
** of computation. The return pointer points to a static buffer that
** is overwritten by subsequent calls to this function.
*/
char *sha3sum_finish(Blob *pOut){
static char zOut[132];
DigestToBase16(SHA3Final(&incrCtx), zOut, incrInit/8);
if( pOut ){
blob_zero(pOut);
blob_append(pOut, zOut, incrInit/4);
}
incrInit = 0;
return zOut;
}
/*
** Compute the SHA3 checksum of a file on disk. Store the resulting
** checksum in the blob pCksum. pCksum is assumed to be initialized.
**
** Return the number of errors.
*/
int sha3sum_file(const char *zFilename, int eFType, int iSize, Blob *pCksum){
FILE *in;
SHA3Context ctx;
char zBuf[10240];
if( eFType==RepoFILE && file_islink(zFilename) ){
/* Instead of file content, return sha3 of link destination path */
Blob destinationPath;
int rc;
blob_read_link(&destinationPath, zFilename);
rc = sha3sum_blob(&destinationPath, iSize, pCksum);
blob_reset(&destinationPath);
return rc;
}
in = fossil_fopen(zFilename,"rb");
if( in==0 ){
return 1;
}
SHA3Init(&ctx, iSize);
for(;;){
int n;
n = fread(zBuf, 1, sizeof(zBuf), in);
if( n<=0 ) break;
SHA3Update(&ctx, (unsigned char*)zBuf, (unsigned)n);
}
fclose(in);
blob_zero(pCksum);
blob_resize(pCksum, iSize/4);
DigestToBase16(SHA3Final(&ctx), blob_buffer(pCksum), iSize/8);
return 0;
}
/*
** Compute the SHA3 checksum of a blob in memory. Store the resulting
** checksum in the blob pCksum. pCksum is assumed to be either
** uninitialized or the same blob as pIn.
**
** Return the number of errors.
*/
int sha3sum_blob(const Blob *pIn, int iSize, Blob *pCksum){
SHA3Context ctx;
SHA3Init(&ctx, iSize);
SHA3Update(&ctx, (unsigned char*)blob_buffer(pIn), blob_size(pIn));
if( pIn==pCksum ){
blob_reset(pCksum);
}else{
blob_zero(pCksum);
}
blob_resize(pCksum, iSize/4);
DigestToBase16(SHA3Final(&ctx), blob_buffer(pCksum), iSize/8);
return 0;
}
#if 0 /* NOT USED */
/*
** Compute the SHA3 checksum of a zero-terminated string. The
** result is held in memory obtained from mprintf().
*/
char *sha3sum(const char *zIn, int iSize){
SHA3Context ctx;
char zDigest[132];
SHA3Init(&ctx, iSize);
SHA3Update(&ctx, (unsigned const char*)zIn, strlen(zIn));
DigestToBase16(SHA3Final(&ctx), zDigest, iSize/8);
return mprintf("%s", zDigest);
}
#endif
/*
** COMMAND: sha3sum*
**
** Usage: %fossil sha3sum FILE...
**
** Compute an SHA3 checksum of all files named on the command-line.
** If a file is named "-" then take its content from standard input.
**
** To be clear: The official NIST FIPS-202 implementation of SHA3
** with the added 01 padding is used, not the original Keccak submission.
**
** Options:
** --224 Compute a SHA3-224 hash
** --256 Compute a SHA3-256 hash (the default)
** --384 Compute a SHA3-384 hash
** --512 Compute a SHA3-512 hash
** --size N An N-bit hash. N must be a multiple of 32 between
** 128 and 512.
** -h|--dereference If FILE is a symbolic link, compute the hash on
** the object pointed to, not on the link itself.
**
** See also: [[md5sum]], [[sha1sum]]
*/
void sha3sum_test(void){
int i;
Blob in;
Blob cksum = empty_blob;
int iSize = 256;
int eFType = SymFILE;
if( find_option("dereference","h",0) ) eFType = ExtFILE;
if( find_option("224",0,0)!=0 ) iSize = 224;
else if( find_option("256",0,0)!=0 ) iSize = 256;
else if( find_option("384",0,0)!=0 ) iSize = 384;
else if( find_option("512",0,0)!=0 ) iSize = 512;
else{
const char *zN = find_option("size",0,1);
if( zN!=0 ){
int n = atoi(zN);
if( n%32!=0 || n<128 || n>512 ){
fossil_fatal("--size must be a multiple of 64 between 128 and 512");
}
iSize = n;
}
}
verify_all_options();
for(i=2; i<g.argc; i++){
if( g.argv[i][0]=='-' && g.argv[i][1]==0 ){
blob_read_from_channel(&in, stdin, -1);
sha3sum_blob(&in, iSize, &cksum);
}else if( sha3sum_file(g.argv[i], eFType, iSize, &cksum) > 0 ){
fossil_fatal("Cannot read file: %s", g.argv[i]);
}
fossil_print("%s %s\n", blob_str(&cksum), g.argv[i]);
blob_reset(&cksum);
}
}