SHA3をGPUで並列処理を行うために OpenSSL のソースを読む（1）

# はじめに
なんで、OpenSSLのソースを読んでみようかと思った経緯なのですが、一昔前まだイーサリアムでマイニングができていたころ、自分でマイニングのソフトを開発できないかと思っていたことがありまして、結局開発する前にイーサリアムがPoSに移行してしまった為に作ることあきらめてしまいました。

しかし、今思うと自分でマイニングソフトを開発することは実質的な目的（ここではマイニング）以外にもプログラミングの探求としては良い題材ではないかと考え、実際に開発してみる事にしました。

イーサリアムは暗号化アルゴリズムとしてSHA3を使用しており、与えられたブロックヘッダーと任意の数を用いてハッシュ値を生成し、上位の桁に0が連続するようなハッシュ値が生成されるように任意の数を変えながら何回も計算するというものです。

何回もSHA3の暗号化を実行する為、任意の数を配列化しGPUで並行して計算するというのがGPUマイニングになります。

イーサリアムのマイニングは Ethminerという標準のマイニングソフトがあったため、それを使ってマイニングをしていたのですが、 NiceHashなどは独自のマイニングソフトを作ったり、Nvidiaのマイニング規制を掻い潜るようなマイニングソフトも出てきました。

# アプローチ
今回SHA3をGPUを使って並行で演算できないかを試みたいと思います。
まずはSHA3の仕組みを理解し、C言語で実装しなければなりません。しかし、NIST の論文を読んでも全くちんぷんかんぷん実装するに至っておりませんでした。
https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf

まずは、スポンジに詰める部分だけでも実装して見ようかと考えたのですが、なかなか手が進まなかったのを思い出します。

その後、しばらく手を付けていなかったのですが、そういえばOpenSSLでSHA3の暗号化ができるので、この中にソースがあるんじゃないかと思いました。

OpenSSLのSHA3の部分だけをうまく抜き出すことができれば、SHA3を実装したのと同じことになります。
なので、「OpenSSLからSHA3をぶっこ抜く」というアプローチで作業を進めてみようと思います。

# GitHubからClone
OpenSSLのソースコードは、GitHubにオープンソースとしてホストされており、git を使って Clone することができます。
https://github.com/openssl/openssl

# ソースを確認
まずはソースを確認して、どこに何があるのかを把握したいと思います。
OpenSSL はC言語で開発されているようなので、鉄則である main 関数がどこにあるのか探してみたいと思います。
main 関数は apps/openssl.c にありました。

```apps/openssl.c
int main(int argc, char *argv[])
{
    FUNCTION f, *fp;
    LHASH_OF(FUNCTION) *prog = NULL;
    char *pname;
    const char *fname;
    ARGS arg;
    int global_help = 0;
    int ret = 0;

    arg.argv = NULL;
    arg.size = 0;
```

main 関数では実行時引数を分割して解析しているようです。help の場合だけ詳細に書かれている様なのですが、help 以外は do_cmd() で処理をしているようです。

```apps/openssl.c
    /* If there's a command, run with that, otherwise "help". */
    ret = argc == 0 || global_help
        ? do_cmd(prog, 1, help_argv)
        : do_cmd(prog, argc, argv);
```

do_cmd() 関数は同じ openssl.c 内にあります。

```apps/openssl.c

static int do_cmd(LHASH_OF(FUNCTION) *prog, int argc, char *argv[])
{
    FUNCTION f, *fp;

    if (argc <= 0 || argv[0] == NULL)
        return 0;

```

do_cmd() 内では何を行っているかというと lh_FUNCTION_retrieve() に渡しています。
```apps/openssl.c
    f.name = argv[0];
    if (CHECK_AND_SKIP_PREFIX(f.name, "no-")) {
        /*
         * User is asking if foo is unsupported, by trying to "run" the
         * no-foo command.  Strange.
         */
        if (lh_FUNCTION_retrieve(prog, &f) == NULL) {
            BIO_printf(bio_out, "%s\n", argv[0]);
            return 0;
        }
        BIO_printf(bio_out, "%s\n", argv[0] + 3);
        return 1;
    }
```

openssl の実行時引数は下記の様な構造になっており、いろいろな暗号化アルゴリズムを処理できるようになっています。

```shell
$ ./openssl --help
help:

Standard commands
asn1parse         ca                ciphers           cmp
cms               crl               crl2pkcs7         dgst
dhparam           dsa               dsaparam          ec
ecparam           enc               engine            errstr
fipsinstall       gendsa            genpkey           genrsa
help              info              kdf               list
mac               nseq              ocsp              passwd
pkcs12            pkcs7             pkcs8             pkey
pkeyparam         pkeyutl           prime             rand
rehash            req               rsa               rsautl
s_client          s_server          s_time            sess_id
smime             speed             spkac             srp
storeutl          ts                verify            version
x509

Message Digest commands (see the `dgst' command for more details)
blake2b512        blake2s256        md4               md5
mdc2              rmd160            sha1              sha224
sha256            sha3-224          sha3-256          sha3-384
sha3-512          sha384            sha512            sha512-224
sha512-256        shake128          shake256          sm3

Cipher commands (see the `enc' command for more details)
aes-128-cbc       aes-128-ecb       aes-192-cbc       aes-192-ecb
aes-256-cbc       aes-256-ecb       aria-128-cbc      aria-128-cfb
aria-128-cfb1     aria-128-cfb8     aria-128-ctr      aria-128-ecb
aria-128-ofb      aria-192-cbc      aria-192-cfb      aria-192-cfb1
aria-192-cfb8     aria-192-ctr      aria-192-ecb      aria-192-ofb
aria-256-cbc      aria-256-cfb      aria-256-cfb1     aria-256-cfb8
aria-256-ctr      aria-256-ecb      aria-256-ofb      base64
bf                bf-cbc            bf-cfb            bf-ecb
bf-ofb            camellia-128-cbc  camellia-128-ecb  camellia-192-cbc
camellia-192-ecb  camellia-256-cbc  camellia-256-ecb  cast
cast-cbc          cast5-cbc         cast5-cfb         cast5-ecb
cast5-ofb         des               des-cbc           des-cfb
des-ecb           des-ede           des-ede-cbc       des-ede-cfb
des-ede-ofb       des-ede3          des-ede3-cbc      des-ede3-cfb
des-ede3-ofb      des-ofb           des3              desx
idea              idea-cbc          idea-cfb          idea-ecb
idea-ofb          rc2               rc2-40-cbc        rc2-64-cbc
rc2-cbc           rc2-cfb           rc2-ecb           rc2-ofb
rc4               rc4-40            seed              seed-cbc
seed-cfb          seed-ecb          seed-ofb          sm4-cbc
sm4-cfb           sm4-ctr           sm4-ecb           sm4-ofb

```

さらにソースの中から lh_FUNCTION_retrieve 関数がどこで定義されているのかを調べます。

```shell
$ grep -r lh_FUNCTION_retrieve .
```

grep で探してみたのですが、関数定義らしいものが出てこないので、 Google で検索してみたところ、マクロで定義されているようで最終的には lh_FUNCTION_retrieve　は OPENSSL_LH_retrieve を呼出しているようです。
OPENSSL_LH_retrieve 関数ではさらに getrn 関数を呼び出しているようです。

```crypto/lhash/lhash.c
void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data)
{
    unsigned long hash;
    OPENSSL_LH_NODE **rn;

    if (lh->error != 0)
        lh->error = 0;

    rn = getrn(lh, data, &hash);

    return *rn == NULL ? NULL : (*rn)->data;
}
```

getrn 関数は同じ lhash.c 内で定義されており、OPENSSL_LH_COMPFUNC の構造体を使って処理を行っています。

```crypto/lhash/lhash.c
static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh,
                               const void *data, unsigned long *rhash)
{
    OPENSSL_LH_NODE **ret, *n1;
    unsigned long hash, nn;
    OPENSSL_LH_COMPFUNC cf;

    hash = (*(lh->hash)) (data);
    *rhash = hash;

    nn = hash % lh->pmax;
    if (nn < lh->p)
        nn = hash % lh->num_alloc_nodes;

    cf = lh->comp;
    ret = &(lh->b[(int)nn]);
    for (n1 = *ret; n1 != NULL; n1 = n1->next) {
        if (n1->hash != hash) {
            ret = &(n1->next);
            continue;
        }
        if (cf(n1->data, data) == 0)
            break;
        ret = &(n1->next);
    }
    return ret;
}
```

ここから OPENSSL_LH_COMPFUNC の定義を探すことができず、手詰まりに。

# SHA3 の神髄に迫る
では、目的に SHA3 がどこで処理されているのかを確認します。
SHA3は、crypt/sha/sha3.c で処理されており下記の様な定義があります。

```crypt/sha/sha3.c
#include <string.h>
#include "internal/sha3.h"

void SHA3_squeeze(uint64_t A[5][5], unsigned char *out, size_t len, size_t r);

void ossl_sha3_reset(KECCAK1600_CTX *ctx)
{
    memset(ctx->A, 0, sizeof(ctx->A));
    ctx->bufsz = 0;
}

int ossl_sha3_init(KECCAK1600_CTX *ctx, unsigned char pad, size_t bitlen)
{
    size_t bsz = SHA3_BLOCKSIZE(bitlen);

    if (bsz <= sizeof(ctx->buf)) {
        ossl_sha3_reset(ctx);
        ctx->block_size = bsz;
        ctx->md_size = bitlen / 8;
        ctx->pad = pad;
        return 1;
    }

    return 0;
}
```

ossl_sha3_init を呼出している個所を探すと下記のファイルが出てきました。

```
$ grep -r ossl_sha3_init .
./providers/implementations/digests/sha3_prov.c:    ossl_sha3_init(ctx, pad, bitlen);
```

マクロ定義の一部に組み込まれているようで何とも奥が深い感じがします。

```providers/implementations/digests/sha3_prov.c
#define SHA3_newctx(typ, uname, name, bitlen, pad)                             \
static OSSL_FUNC_digest_newctx_fn name##_newctx;                               \
static void *name##_newctx(void *provctx)                                      \
{                                                                              \
    KECCAK1600_CTX *ctx = ossl_prov_is_running() ? OPENSSL_zalloc(sizeof(*ctx)) \
                                                : NULL;                        \
                                                                               \
    if (ctx == NULL)                                                           \
        return NULL;                                                           \
    ossl_sha3_init(ctx, pad, bitlen);                                          \
    SHA3_SET_MD(uname, typ)                                                    \
    return ctx;                                                                \
}
```

crypt/sha/sha3.c で定義されている関数を組み合わせて使用するとSHA3の暗号化はできそうですが、さらに深堀をしていきたいと思います。
最終目的はSHA3の暗号化処理をGPUで置き換えるという所なので。

重要なのはNISTの論文にも出てきた KECCAK1600_CTX にあるようです。
KECCAK1600_CTX をソースの中から探すことにしましょう。

KECCAK1600_CTX は keccak_st 構造体として定義されていました。この中にSHA3暗号化に必要なデータが定義されています。

```include/internal/sha3.h
typedef struct keccak_st KECCAK1600_CTX;

typedef size_t (sha3_absorb_fn)(void *vctx, const void *inp, size_t len);
typedef int (sha3_final_fn)(unsigned char *md, void *vctx);

typedef struct prov_sha3_meth_st
{
    sha3_absorb_fn *absorb;
    sha3_final_fn *final;
} PROV_SHA3_METHOD;

struct keccak_st {
    uint64_t A[5][5];
    size_t block_size;          /* cached ctx->digest->block_size */
    size_t md_size;             /* output length, variable in XOF */
    size_t bufsz;               /* used bytes in below buffer */
    unsigned char buf[KECCAK1600_WIDTH / 8 - 32];
    unsigned char pad;
    PROV_SHA3_METHOD meth;
};
```

また、重要な情報として、SHAのロジックのほとんどはマクロの組み合わせになっており、 crypt/sha/sha_local.h に各所で出てくるマクロが定義されています。
（掛け算やローテート等）

KECCAK1600_CTX が構造体であり、SHA3 の処理に必要なデータの固まりだという事が理解できた上で、crypt/sha/sha3.c を読むと、この中では単純に構造体の初期化と演算をハンドリングしているだけという事が分かります。

ossl_sha3_update関数内ではSHA3_absorb()を実行しておりこれが処理の中核になると考えられます。


```crypt/sha/sha3.c
int ossl_sha3_update(KECCAK1600_CTX *ctx, const void *_inp, size_t len)
{
    const unsigned char *inp = _inp;
    size_t bsz = ctx->block_size;
    size_t num, rem;

    if (len == 0)
        return 1;

    if ((num = ctx->bufsz) != 0) {      /* process intermediate buffer? */
        rem = bsz - num;

        if (len < rem) {
            memcpy(ctx->buf + num, inp, len);
            ctx->bufsz += len;
            return 1;
        }
        /*
         * We have enough data to fill or overflow the intermediate
         * buffer. So we append |rem| bytes and process the block,
         * leaving the rest for later processing...
         */
        memcpy(ctx->buf + num, inp, rem);
        inp += rem, len -= rem;
        (void)SHA3_absorb(ctx->A, ctx->buf, bsz, bsz);
        ctx->bufsz = 0;
        /* ctx->buf is processed, ctx->num is guaranteed to be zero */
    }

    if (len >= bsz)
        rem = SHA3_absorb(ctx->A, inp, len, bsz);
    else
        rem = len;

    if (rem) {
        memcpy(ctx->buf, inp + len - rem, rem);
        ctx->bufsz = rem;
    }

    return 1;
}
```
SHA3_absorb は crypt/sha/keccak1600.c 内で定義されており、もうこの中は配列の演算を行っているだけとなります。


```crypt/sha/keccak1600.c
size_t SHA3_absorb(uint64_t A[5][5], const unsigned char *inp, size_t len,
                   size_t r)
{
    uint64_t *A_flat = (uint64_t *)A;
    size_t i, w = r / 8;

    assert(r < (25 * sizeof(A[0][0])) && (r % 8) == 0);

    while (len >= r) {
        for (i = 0; i < w; i++) {
            uint64_t Ai = (uint64_t)inp[0]       | (uint64_t)inp[1] << 8  |
                          (uint64_t)inp[2] << 16 | (uint64_t)inp[3] << 24 |
                          (uint64_t)inp[4] << 32 | (uint64_t)inp[5] << 40 |
                          (uint64_t)inp[6] << 48 | (uint64_t)inp[7] << 56;
            inp += 8;

            A_flat[i] ^= BitInterleave(Ai);
        }
        KeccakF1600(A);
        len -= r;
    }

    return len;
}
```

さらに SHA3_absorb この中で KeccakF1600 という関数を呼び出しています。これは何をしているかというと
論文にあった演算を各配列に対して行っているだけとなります。この配列演算はGPUで並列化できそうです。

```crypt/sha/keccak1600.c
static void KeccakF1600(uint64_t A[5][5])
{
    size_t i;

    for (i = 0; i < 24; i++) {
        Theta(A);
        Rho(A);
        Pi(A);
        Chi(A);
        Iota(A, i);
    }
}
```

# つづく
もう、ちょっと頭が焼き切れそうなので今日は一旦ここまでにしようと思います。

次回は、SHA3_absorb や KeccakF1600 の中身が分かってきましたので、実際にNISTの論文と照らし合わせて、論文がどのように実装されているかを紐解いていきたいと思います。