憂鬱な午後のひととき

10月16日_

ROCA:Vlunerable RSA generation

CVE-2017-15361

Infineon Technologies社のチップなどで作られたRSA鍵に脆弱性. OpenSSLで作ったものは大丈夫らしい.

公開鍵nを小さい素数(3~167)で割った余りが特定の値になったときに危ないもよう. rocaで確認できる.

該当する公開鍵か否かをチェックしているコードはhas_fingerprint_realあたり.

primes # 3から167までの素数のテーブル
prints # 対応するなんらかの数字

n # 公開鍵
for i in range(len(primes)):
     if (1 << (n % primes[i])) & prints[i] == 0:
         return False # 安全
return True # 安全じゃない

とりあえず自分に関係してるものは大丈夫そうだった.

10月10日_

wrapper class

BLS demoのAPIがWASMの_malloc, _freeを使ってるのでとても使いにくかったのでC++ライクなクラスを被せた.

classがmallocのポインタを保持してるとdestructorでfreeしないといけないのでUint32Array a_で持つことにした.

freeは気にしなくてもよいがメソッド呼び出しの度にmallocしてそのポインタにa_にコピーしないといけない. でも使い勝手はずっとよくなるのでその方がよいだろう.

うまく行きそうなのでSHEでもその方針で進める.

10月8日_

strnlen

strnlen(const char *s, size_t n)はsが区間[0, n)に'\0'を含んでいないときはnを返すのだけど, PVS-Studioは常にn未満を返すという前提の警告を出していた. そのせいで正しいコードがエラーになっていたので指摘して次のバーションで修正してもらうことになった.

10月6日_

128bit整数に対するbsr

元ネタはナンプレの正規化 ステップ・バイ・ステップ その5.

__builtin_clzlはbsrのintrinsicなのだけど0かどうかを事前にチェックしないといけない. bsr自体はその機能を持っているので冗長. 更に結果を反転させてるのでそれも無駄だから嫌いなintrinsicの一つ(cf. bsfとbsr). 実際, (値の受け渡しは呼び出し規約が分かりにくくなるのでポインタに変更した上で),

// typedef unsigned __int128 mbit;
void left_most_bit(mbit* v) {
  uint64_t *a = reinterpret_cast<uint64_t*>(v);
  if (a[1]) {
    a[0] = 0;
    a[1] = 1ull << (63 - __builtin_clzl(a[1]));
  } else if (a[0]) {
    a[0] = 1ull << (63 - __builtin_clzl(a[0]));
    a[1] = 0;
  }
}

はclangだと

left_most_bit:
    mov    rax,[rdi+0x8]
    test   rax,rax
    je     .low
    mov    QWORD [rdi],0x0
    lzcnt  rax,rax
    xor    eax,0x3f
    mov    ecx,0x1
    shlx   rax,rcx,rax
    mov    [rdi+0x8],rax
    ret
.low:
    mov    rax,[rdi]
    test   rax,rax
    je     .zero
    lzcnt  rax,rax
    xor    eax,0x3f
    mov    ecx,0x1
    shlx   rax,rcx,rax
    mov    QWORD PTR [rdi],rax
    mov    QWORD PTR [rdi+0x8],0x0
.zero:
    ret

となった. 今回の場合はVCの_BitScanReverse64がスマートだと思う.

void left_most_bit2(mbit* v) {
    uint64_t *a = reinterpret_cast<uint64_t*>(v);
    unsigned long idx;
    if (_BitScanReverse64(&idx, a[1])) {
        a[0] = 0;
        a[1] = uint64_t(1) << idx;
    } else if (_BitScanReverse64(&idx, a[0])) {
        a[0] = uint64_t(1) << idx;
        a[1] = 0;
    }
}

これならxorも条件分岐も減ったコードが生成される. x64 Linux用のNASMで書くとこう.

global left_most_bit

segment .text
left_most_bit:
    bsr rcx, [rdi + 8]
    mov edx, 1
    je .low
    mov qword [rdi], 0
    shl rdx, cl
    mov [rdi + 8], rdx
    ret
.low:
    bsr rcx, [rdi]
    je .zero
    mov qword [rdi + 8], 0
    shl rdx, cl
    mov [rdi], rdx
.zero:
    ret
10月5日_

PVS-Studio

去年Microsoft MVPを受賞したときに1年間使わせてもらっていた. いろいろバグが見つかってよかったのだがライセンスが切れてしまった.

それでLinux版が欲しいので値段を聞いたら何故かもう1年分ライセンスをくれた.

とてもありがたいので早速WalBで試したらいくつかポカミスが見つかったので修正. 多分そのうちマージされる.

こないだのblueborneのAndroidのRCEのバグもこれを試してたら見つけられていたかもしれない.

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct {
    char a;
    int b;
    long long int c;
} X;

X *func() {
    X *p = (X*)malloc(sizeof(X));
    if (p == NULL) return 0;
    memset(((unsigned char*) p + 1), 0, sizeof(X));
    return p;
}

A call of the 'memset' function will lead to overflow of the buffer '(unsigned char*)p + 1'.

10月4日_

最適化

ate-pairingmclは殆ど同じロジック・コードなのになんで約1.5倍も速度差があるのかずっと気になってた.

それぞれの関数自体はそんなに差がない. いろいろ細かく調べてみたところ, どうやらate-pairingでやってる低レイヤーの関数の呼び出し規約を独自にしてレジスタの退避復元を省略している部分が結構効いているようだ.

うーん, それをLLVMでやるのは辛そう.

10月2日_

ブラウザ上でSHE

ペアリングベースの一度だけ乗算可能なSHEが動いた(she.html). テーブルサイズの設定を工夫しないと初期化に時間がかかったりエラーになるけどまずはめでたい.

10月1日_

WASM

int64_tを受け渡しするAPIだと途中でint32_tに切られたりしていろいろ不整合がでるようだ. 32ビット整数しかやりとりしないのが無難.

JavaScriptには64ビット整数が無いのにWASMにはあるのがまたややこしい.


御意見は光成滋生<herumi@nifty.com>までお願いします