Keccak Cryptanalysis

sha3.cpp

#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>

typedef unsigned char UINT8;
typedef unsigned short UINT16;
typedef unsigned int UINT32;
typedef unsigned long long UINT64;
typedef UINT64 LaneValue;

class KeccakF {
    protected:
        unsigned int width;
        unsigned int laneSize;
        int startRoundIndex;
        unsigned int nrRounds;
        std::vector<int> rhoOffsets;
        std::vector<LaneValue> roundConstants;
        LaneValue mask;
    public:
        KeccakF(unsigned int aWidth);
        void inverse(UINT8 *state) const;
        static unsigned int index(int x, int y);
        static unsigned int index(int x);
        template<class Lane> void inverse(std::vector<Lane>& state) const;
        template<class Lane> void inverseRound(std::vector<Lane>& A, int roundIndex) const;
        template<class Lane> void inverseChi(std::vector<Lane>& A) const;
        template<class Lane> void inverseTheta(std::vector<Lane>& A) const;
        template<class Lane> void inversePi(std::vector<Lane>& A) const;
        static void inversePi(unsigned int X, unsigned int Y, unsigned int& x, unsigned int& y);
        template<class Lane> void inverseRho(std::vector<Lane>& A) const;
        inline unsigned int inverseRho(unsigned int x, unsigned int y, unsigned int z) const { return (640+z-rhoOffsets[index(x,y)])%laneSize; }
        template<class Lane> void iota(std::vector<Lane>& A, int roundIndex) const;
        template<class Lane> void ROL(Lane& L, int offset) const;
        void ROL(LaneValue& L, int offset) const;
        void fromBytesToLanes(const UINT8 *in, std::vector<LaneValue>& out) const;
        void fromLanesToBytes(const std::vector<LaneValue>& in, UINT8 *out) const;
    private:
        void initializeRoundConstants();
        void initializeRhoOffsets();
};

template<class Lane> void KeccakF::inverse(std::vector<Lane>& state) const {
    for(int i=startRoundIndex+nrRounds-1; i>=startRoundIndex; i--) {
        inverseRound(state, i);
    }
}

template<class Lane> void KeccakF::inverseRound(std::vector<Lane>& state, int roundIndex) const {
    iota(state, roundIndex);
    inverseChi(state);
    inversePi(state);
    inverseRho(state);
    inverseTheta(state);
}

template<class Lane> void KeccakF::inverseChi(std::vector<Lane>& A) const {
    for(unsigned int y=0; y<5; y++) {
        unsigned int length = 5;
        std::vector<Lane> C(length);
        for(unsigned int x=0; x<length; x++) { C[index(x)] = A[index(x,y)]; }
        for(unsigned int x=0; x<(3*(length-1)/2); x++) {
            unsigned int X = (length-2)*x;
            A[index(X,y)] = C[index(X)] ^ (A[index(X+2,y)] & (~C[index(X+1)]));
        }
    }
}

template<class Lane> void KeccakF::inverseTheta(std::vector<Lane>& A) const {
    std::vector<Lane> C(5);
    for(unsigned int x=0; x<5; x++) {
        C[x] = A[index(x,0)];
        for(unsigned int y=1; y<5; y++) {
            C[x] ^= A[index(x,y)];
        }
    }
    const LaneValue inversePositions64[5] = { 
        0xDE26BC4D789AF134ULL, 0x09AF135E26BC4D78ULL, 0xEBC4D789AF135E26ULL, 0x7135E26BC4D789AFULL, 0xCD789AF135E26BC4ULL
    };
    std::vector<LaneValue> inversePositions(5, 0);
    for(unsigned int z=0; z<64; z+=laneSize) {
        for(unsigned int x=0; x<5; x++) {
            inversePositions[x] ^= inversePositions64[x] >> z;
        }
    }
    for(unsigned int z=0; z<laneSize; z++) {
        for(unsigned int xOff=0; xOff<5; xOff++) {
           for(int x=0; x<5; x++) {
               for(unsigned int y=0; y<5; y++) {
                   if ((inversePositions[xOff] & 1) != 0) {
                      A[index(x, y)] ^= C[index(x-xOff)];
                   }
               }
           }
        }
        for(unsigned int xOff=0; xOff<5; xOff++) {
            ROL(C[xOff], 1);
            inversePositions[xOff] >>= 1;
        }
    }
}

template<class Lane> void KeccakF::inversePi(std::vector<Lane>& A) const {
    std::vector<Lane> a(A);
    for(unsigned int X=0; X<5; X++) {
        for(unsigned int Y=0; Y<5; Y++) {
            unsigned int x, y;
            inversePi(X, Y, x, y);
            A[index(x,y)] = a[index(X,Y)];
        }
    }
}

template<class Lane> void KeccakF::inverseRho(std::vector<Lane>& A) const {
    for(unsigned int x=0; x<5; x++) {
        for(unsigned int y=0; y<5; y++) {
            ROL(A[index(x,y)], -rhoOffsets[index(x,y)]);
        }
    }
}

template<class Lane> void KeccakF::iota(std::vector<Lane>& A, int roundIndex) const {
    unsigned int ir = (unsigned int)(((roundIndex % 255) + 255) % 255);
    A[index(0,0)] ^= roundConstants[ir];
}

KeccakF::KeccakF(unsigned int aWidth): width(1600), laneSize(0), startRoundIndex(0), nrRounds(0), rhoOffsets{}, roundConstants{}, mask(0) {
    width = aWidth;
    laneSize = width/25;
    nrRounds /* initializeNominalNumberOfRounds */ = 24;
    startRoundIndex = 0;
    mask = (LaneValue(~0)) >> (64-laneSize);
    initializeRhoOffsets();
    initializeRoundConstants();
}

unsigned int KeccakF::index(int x, int y) {
    x %= 5;
    if (x<0) { x += 5; }
    y %= 5;
    if (y<0) { y += 5; }
    return(x + (5*y));
}

unsigned int KeccakF::index(int x) {
    x %= 5;
    if (x<0) { x += 5; }
    return x;
}

void KeccakF::inverse(UINT8 *state) const {
    std::vector<LaneValue> A(25);
    fromBytesToLanes(state, A);
    inverse(A);
    fromLanesToBytes(A, state);
}

void KeccakF::inversePi(unsigned int X, unsigned int Y, unsigned int& x, unsigned int& y) {
    x = (1*X+3*Y)%5;
    y = (1*X+0*Y)%5;
}

void KeccakF::ROL(LaneValue& L, int offset) const {
    offset %= (int)laneSize;
    if (offset < 0) { offset += laneSize; }
    if (offset != 0) {
        L &= mask;
        L = (((LaneValue)L) << offset) ^ (((LaneValue)L) >> (laneSize-offset));
    }
    L &= mask;
}

void KeccakF::fromBytesToLanes(const UINT8 *in, std::vector<LaneValue>& out) const {
    out.resize(25);
    if ((laneSize == 1) || (laneSize == 2) || (laneSize == 4) || (laneSize == 8)) {
        for(unsigned int i=0; i<25; i++) {
            out[i] = (in[i*laneSize/8] >> ((i*laneSize) % 8)) & mask;
        }
    }
    else if ((laneSize == 16) || (laneSize == 32) || (laneSize == 64)) {
        for(unsigned int i=0; i<25; i++) {
            out[i] = 0;
            for(unsigned int j=0; j<(laneSize/8); j++) {
                out[i] |= LaneValue((UINT8)(in[i*laneSize/8+j])) << (8*j);
            }
        }
    }
}

void KeccakF::fromLanesToBytes(const std::vector<LaneValue>& in, UINT8 *out) const {
    if ((laneSize == 1) || (laneSize == 2) || (laneSize == 4) || (laneSize == 8)) {
        for(unsigned int i=0; i<(25*laneSize+7)/8; i++) {
            out[i] = 0;
        }
        for(unsigned int i=0; i<25; i++) {
            out[i*laneSize/8] |= in[i] << ((i*laneSize) % 8);
        }
    }
    else if ((laneSize == 16) || (laneSize == 32) || (laneSize == 64)) {
        for(unsigned int i=0; i<25; i++) {
            for(unsigned int j=0; j<(laneSize/8); j++) {
                out[i*(laneSize/8)+j] = (UINT8)((in[i] >> (8*j)) & 0xFF);
            }
        }
    }
}

void KeccakF::initializeRoundConstants() {
    roundConstants.clear();
    UINT8 LFSRstate = 0x01;
    for (unsigned int i = 0; i < 255; i++) {
        LaneValue c = 0;
        for (unsigned int j = 0; j < 7; j++) {
            unsigned int bitPosition = (1 << j) - 1;
            bool result /* unused LFSR86540 */ = (LFSRstate & 0x01) != 0;
            LFSRstate = (LFSRstate & 0x80) != 0 ? ((LFSRstate << 1) ^ 0x71) : (LFSRstate << 1);
            if (result) { c ^= (LaneValue)1 << bitPosition; }
        }
        roundConstants.push_back(c & mask);
    }
}

void KeccakF::initializeRhoOffsets() {
    rhoOffsets.resize(25);
    rhoOffsets[index(0, 0)] = 0;
    unsigned int x = 1;
    unsigned int y = 0;
    for(unsigned int t=0; t<24; t++) {
        rhoOffsets[index(x, y)] = ((t+1)*(t+2)/2) % laneSize;
        unsigned int newX = (0*x + 1*y)%5;
        unsigned int newY = (2*x + 3*y)%5;
        x = newX; y = newY;
    }
}

int main() {
    UINT8 state[64] = {13, 110, 87, 117, 5, 245, 12, 172, 152, 133, 227, 26, 112, 218, 139, 180, 124, 89, 221, 119, 30, 125, 114, 46, 19, 148, 157, 105, 46, 96,
        123, 152, 227, 111, 178, 185, 33, 118, 28, 163, 127, 148, 251, 194, 250, 40, 64, 187, 254, 221, 130, 94, 79, 101, 181, 24, 125, 13, 136, 52, 32, 53, 43, 227};
    UINT8 hash[136] __attribute__((unused)) = {179, 248, 22, 246, 50, 243, 86, 150, 221, 102, 154, 9, 82, 242, 140, 95, 99, 55, 164, 189, 43, 183, 218, 221, 234,
        233, 179, 100, 43, 19, 168, 84, 68, 28, 83, 228, 82, 140, 70, 125, 145, 72, 79, 225, 35, 41, 103, 34, 55, 182, 39, 3, 169, 85, 151, 196, 36, 239, 247, 172,
        4, 237, 247, 9, 97, 28, 161, 53, 249, 179, 134, 104, 186, 45, 74, 95, 69, 175, 246, 83, 43, 137, 173, 59, 236, 101, 251, 197, 53, 1, 14, 29, 91, 239, 16, 16,
        177, 159, 153, 200, 165, 243, 119, 140, 26, 88, 83, 126, 17, 164, 40, 86, 89, 157, 88, 253, 127, 247, 230, 202, 75, 78, 151, 29, 133, 160, 121, 7, 18, 163, 9,
        120, 63, 140, 25, 238};
    KeccakF keccakF(400*4);
    keccakF.inverse(state); // Working on https://godbolt.org with x86-64 gcc 13.2 -fstack-protector -std=c++17
    std::cout << reinterpret_cast<char*>(state) << std::endl; // Congratulations, ...
    return 0; // g++ -fstack-protector -std=c++11 -Wall -Weffc++ -Werror -Wextra -pedantic -g -O0 -unroll-loops sha3.cpp -o sha3 && ./sha3
}