はじめに
なんで、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 にありました。
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() で処理をしているようです。
/* 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 内にあります。
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() に渡しています。
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 の実行時引数は下記の様な構造になっており、いろいろな暗号化アルゴリズムを処理できるようになっています。
$ ./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 関数がどこで定義されているのかを調べます。
$ grep -r lh_FUNCTION_retrieve .
grep で探してみたのですが、関数定義らしいものが出てこないので、 Google で検索してみたところ、マクロで定義されているようで最終的には lh_FUNCTION_retrieve は OPENSSL_LH_retrieve を呼出しているようです。
OPENSSL_LH_retrieve 関数ではさらに getrn 関数を呼び出しているようです。
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 の構造体を使って処理を行っています。
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 で処理されており下記の様な定義があります。
#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);
マクロ定義の一部に組み込まれているようで何とも奥が深い感じがします。
#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暗号化に必要なデータが定義されています。
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()を実行しておりこれが処理の中核になると考えられます。
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 内で定義されており、もうこの中は配列の演算を行っているだけとなります。
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で並列化できそうです。
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の論文と照らし合わせて、論文がどのように実装されているかを紐解いていきたいと思います。