status-im / nim-blscurve

Nim implementation of BLS signature scheme (Boneh-Lynn-Shacham) over Barreto-Lynn-Scott (BLS) curve BLS12-381
Apache License 2.0
26 stars 11 forks source link

Stack corruption due to ECP_mul temporary #43

Closed mratsim closed 4 years ago

mratsim commented 4 years ago

A followup on #40 and another debugging session on https://github.com/status-im/nim-beacon-chain/pull/780

By instrumenting privToPub and ECP_MUL with

func privToPub*(secretKey: SecretKey): PublicKey =
  ## Generates a public key from a secret key
  debugEcho "Entering privToPub"
  debugEcho "  seckey: ", secretKey.toHex()
  result.point = generator1()
  result.point.mul(secretKey.intVal)
  debugEcho "  pubkey: ", result.toHex()
  debugEcho "Exiting privToPub"
void ECP_BLS381_mul(ECP_BLS381 *P,BIG_384_58 e)
{
#if CURVETYPE_BLS381==MONTGOMERY
   // [...]
#else
    /* fixed size windows */
    int i,nb,s,ns;
    BIG_384_58 mt,t;
    ECP_BLS381 Q,W[8],C;
    sign8 w[1+(NLEN_384_58*BASEBITS_384_58+3)/4];

    if (ECP_BLS381_isinf(P)) return;
    if (BIG_384_58_iszilch(e))
    {
        ECP_BLS381_inf(P);
        return;
    }

    ECP_BLS381_affine(P);

    /* precompute table */

    ECP_BLS381_copy(&Q,P);
    ECP_BLS381_dbl(&Q);

    ECP_BLS381_copy(&W[0],P);

    for (i=1; i<8; i++)
    {
        ECP_BLS381_copy(&W[i],&W[i-1]);
        ECP_BLS381_add(&W[i],&Q);
    }

//printf("W[1]= ");ECP_output(&W[1]); printf("\n");

    /* make exponent odd - add 2P if even, P if odd */
    BIG_384_58_copy(t,e);
    s=BIG_384_58_parity(t);
    BIG_384_58_inc(t,1);
    BIG_384_58_norm(t);
    ns=BIG_384_58_parity(t);
    BIG_384_58_copy(mt,t);
    BIG_384_58_inc(mt,1);
    BIG_384_58_norm(mt);
    BIG_384_58_cmove(t,mt,s);
    ECP_BLS381_cmove(&Q,P,ns);
    ECP_BLS381_copy(&C,&Q);

    nb=1+(BIG_384_58_nbits(t)+3)/4;

    printf("ECP_mul:\n");
    printf("  sign8 w[%d]\n", 1+(NLEN_384_58*BASEBITS_384_58+3)/4);
    printf("  nb: %d\n", nb);
    printf("  t: ");
    BIG_384_58_output(t);
    printf("\n");

    /* convert exponent to signed 4-bit window */
    for (i=0; i<nb; i++)
    {
        w[i]=BIG_384_58_lastbits(t,5)-16;
        BIG_384_58_dec(t,w[i]);
        BIG_384_58_norm(t);
        BIG_384_58_fshr(t,4);
    }
    w[nb]=BIG_384_58_lastbits(t,5);

    ECP_BLS381_copy(P,&W[(w[nb]-1)/2]);
    for (i=nb-1; i>=0; i--)
    {
        ECP_BLS381_select(&Q,W,w[i]);
        ECP_BLS381_dbl(P);
        ECP_BLS381_dbl(P);
        ECP_BLS381_dbl(P);
        ECP_BLS381_dbl(P);
        ECP_BLS381_add(P,&Q);
    }
    ECP_BLS381_sub(P,&C); /* apply correction */
#endif
    ECP_BLS381_affine(P);

    printf("Exiting ECP_mul\n");
}

We get the following stacktrace after building beacon_node with

source env.sh
nim c --cc:clang -d:release --import:libbacktrace --verbosity:0 --hints:off --warnings:off --passC:-fsanitize=address --passL:"-fsanitize=address" -o:build/beacon_node_asan beacon_chain/beacon_node
build/beacon_node_asan --nat:extip:127.0.0.1 --data-dir=local_testnet_data/node0 --state-snapshot=local_testnet_data/network_dir/genesis.ssz
INF 2020-03-12 17:19:40+01:00 Initializing networking                    tid=462177 file=eth2_network.nim:148 announcedAddresses=@[/ip4/127.0.0.1/tcp/9000] bootstrapNodes=@[] hostAddress=/ip4/0.0.0.0/tcp/9000
Control socket: /unix/tmp/nim-p2pd-462177-1.sock
Peer ID: 16Uiu2HAm6wkfwKLZor7HvwGbR14n6b7GH7ZjwUj385XpvUHBQmmS
Peer Addrs:
/ip4/127.0.0.1/tcp/9000
INF 2020-03-12 17:19:41+01:00 LibP2P daemon started                      tid=462177 file=eth2_network.nim:179 addresses=@[/ip4/127.0.0.1/tcp/9000] peer=16Uiu2HAm6wkfwKLZor7HvwGbR14n6b7GH7ZjwUj385XpvUHBQmmS
INF 2020-03-12 17:19:41+01:00 Waiting for connections                    topics="beacnde" tid=462177 file=beacon_node.nim:252
INF 2020-03-12 17:19:41+01:00 Starting beacon node                       topics="beacnde" tid=462177 file=beacon_node.nim:909 SECONDS_PER_SLOT=6 SLOTS_PER_EPOCH=8 SPEC_VERSION=0.10.1 cat=init dataDir=local_testnet_data/node0 finalizedRoot=5668f217 finalizedSlot=0 headRoot=5668f217 headSlot=0 pcs=start_beacon_node timeSinceFinalization=-1784 version="0.3.0 (b2faac7, libp2p_daemon)"
 peers: 0 ❯ epoch: 37, slot: 1/8 (297) ❯ finalized epoch: 0 (5668f217)                                                                                                                                                       ETH: 0 Entering privToPub
  seckey: 000000000000000000000000000000005b136035599c4233c2de3ed4e2eb78f1e3bf40cd550b333dc050695878b49075
ECP_mul:
  sign8 w[103]
  nb: 100
  t: d68000000000000000000000000000000005b136035599c4233c2de3ed4e2eb78f1e3bf40cd550b333dc050695878b49077
Exiting ECP_mul
  pubkey: 8a8ce89d5ae099ca6d86c8a25d6f1dc8b5c1d455cd5483699910ada7c9607f568bf5b6971495a99325fe73dc3dd17c6e
Exiting privToPub
WRN 2020-03-12 17:19:41+01:00 Validator not in registry (yet?)           topics="beacnde" tid=462177 file=beacon_node.nim:273 pubKey="real: 0x8a8ce89d5ae099ca6d86c8a25d6f1dc8b5c1d455cd5483699910ada7c9607f568bf5b6971495a99325fe73dc3dd17c6e"
INF 2020-03-12 17:19:41+01:00 Local validator attached                   tid=462177 file=validator_pool.nim:21 pubKey="real: 0x8a8ce89d5ae099ca6d86c8a25d6f1dc8b5c1d455cd5483699910ada7c9607f568bf5b6971495a99325fe73dc3dd17c6e" validator="real: 0x"
 peers: 0 ❯ epoch: 37, slot: 1/8 (297) ❯ finalized epoch: 0 (5668f217)                                                                                                                                                       ETH: 0 Entering privToPub
  seckey: 00000000000000000000000000000000292bcd8b78ffc85782ed9c1052f581cca2c96d80a3c46c2bc1527b3cf188022b
ECP_mul:
  sign8 w[103]
  nb: 104
  t: 0b4907500000000000000000000000000000000292bcd8b78ffc85782ed9c1052f581cca2c96d80a3c46c2bc1527b3cf188022d
=================================================================
==462177==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffedfc8c7e7 at pc 0x5654edbd17e1 bp 0x7ffedfc8bd10 sp 0x7ffedfc8bd08
WRITE of size 1 at 0x7ffedfc8c7e7 thread T0
    #0 0x5654edbd17e0 in ECP_BLS381_mul /home/beta/Programming/Status/nim-beacon-chain/vendor/nim-blscurve/blscurve/csources/64/ecp_BLS381.c:1112:13
    #1 0x5654edfc31c3 in mul__8dasrHsBDivosc1xoLwN9aQcommon /home/beta/Programming/Status/nim-beacon-chain/vendor/nim-blscurve/blscurve/common.nim:297:2
    #2 0x5654edfc31c3 in privToPub__SbUVL7n9atErGXu7gDCy72Q /home/beta/Programming/Status/nim-beacon-chain/vendor/nim-blscurve/blscurve/bls_signature_scheme.nim:99:2
    #3 0x5654edfc5d0e in pubKey__HCx9cqWY5g0ZVsIUBYuD9cVA /home/beta/Programming/Status/nim-beacon-chain/beacon_chain/spec/crypto.nim:101:20
    #4 0x5654ee28ed0b in addLocalValidator__cSSHpZxKVcAbxlaA9bLXQsQ /home/beta/Programming/Status/nim-beacon-chain/beacon_chain/beacon_node.nim:267:11
    #5 0x5654ee290a9e in addLocalValidators__l9bqvDlqEn0zFromo2S35YQ /home/beta/Programming/Status/nim-beacon-chain/beacon_chain/beacon_node.nim:279:13
    #6 0x5654ee2a34dd in start__ZJSNFUSOl2Ftt60X6ooHFQ_2 /home/beta/Programming/Status/nim-beacon-chain/beacon_chain/beacon_node.nim:929:2
    #7 0x5654ee2ad2ce in NimMainModule /home/beta/Programming/Status/nim-beacon-chain/beacon_chain/beacon_node.nim:1172:4
    #8 0x5654ee2af69a in NimMain /home/beta/Programming/Status/nim-beacon-chain/vendor/nim-eth/eth/common/eth_types.nim:595:2
    #9 0x5654ee2af69a in main /home/beta/Programming/Status/nim-beacon-chain/vendor/nim-eth/eth/common/eth_types.nim:602:2
    #10 0x7fda7d270022 in __libc_start_main (/usr/lib/libc.so.6+0x27022)
    #11 0x5654ed6655fd in _start (/home/beta/Programming/Status/nim-beacon-chain/build/beacon_node_asan+0x15f5fd)

Address 0x7ffedfc8c7e7 is located in stack of thread T0 at offset 2759 in frame
    #0 0x5654edbd10bf in ECP_BLS381_mul /home/beta/Programming/Status/nim-beacon-chain/vendor/nim-blscurve/blscurve/csources/64/ecp_BLS381.c:1022

  This frame has 7 object(s):
    [32, 224) 'NQ.i' (line 985)
    [288, 344) 'mt' (line 1059)
    [384, 440) 't' (line 1059)
    [480, 672) 'Q' (line 1060)
    [736, 2272) 'W' (line 1060)
    [2400, 2592) 'C' (line 1060)
    [2656, 2759) 'w' (line 1061) <== Memory access at offset 2759 overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow /home/beta/Programming/Status/nim-beacon-chain/vendor/nim-blscurve/blscurve/csources/64/ecp_BLS381.c:1112:13 in ECP_BLS381_mul
Shadow bytes around the buggy address:
  0x10005bf898a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005bf898b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005bf898c0: f2 f2 f2 f2 f2 f2 f2 f2 f2 f2 f2 f2 f2 f2 f2 f2
  0x10005bf898d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005bf898e0: 00 00 00 00 00 00 00 00 f2 f2 f2 f2 f2 f2 f2 f2
=>0x10005bf898f0: 00 00 00 00 00 00 00 00 00 00 00 00[07]f3 f3 f3
  0x10005bf89900: f3 f3 f3 f3 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005bf89910: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005bf89920: 00 00 00 00 f1 f1 f1 f1 f8 f8 f8 f8 f8 f8 f2 f2
  0x10005bf89930: f2 f2 00 00 f2 f2 00 00 f2 f2 f8 f8 f8 f8 f8 f8
  0x10005bf89940: f8 f8 f8 f8 f8 f8 f8 f8 f8 f8 f8 f8 f8 f8 f8 f8
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==462177==ABORTING

image


Trying to isolate this with the following test cases gives different result

import blscurve/[milagro, common], nimcrypto/utils

proc main3() =

  var okm: DBIG_384
  doAssert okm.fromBytes fromHex"00000000000000000000000000000000292bcd8b78ffc85782ed9c1052f581cca2c96d80a3c46c2bc1527b3cf188022b"

  debugEcho "CurveOrder: ", CURVE_Order.toHex()

  var secretkey: BIG_384
  BIG_384_dmod(secretkey, okm, CURVE_Order)

  echo "seckey: ", secretkey

  var pubkey = generator1()
  pubkey.mul(secretkey)

  echo "publickey: ", pubkey

main3()
CurveOrder: 0000000000000000000000000000000073eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
seckey: 00000000000000000000000000000000292bcd8b78ffc85782ed9c1052f581cca2c96d80a3c46c2bc1527b3cf188022b
ECP_mul:
  sign8 w[103]
  nb: 65
  t: 00000000000000000000000000000000292bcd8b78ffc85782ed9c1052f581cca2c96d80a3c46c2bc1527b3cf188022d
Exiting ECP_mul
publickey: (14773bb3c55136094b5c57afd2bc82df920f18e90494585859b929b1c458422df4e946316d94eb2b36953dc37452ea79, 1449e5104eb4fcf6c19bc20e05412906e26309385dc0c6050a548b1eedc6026aff9bfd1b620eea48e90bb7ca56ec6bef)

Notice that the temporary variable t first bits are not polluted.

mratsim commented 4 years ago

Adding more details in ECP_mul, it seems like e itself (the exponent in ECP_MUL and also the secret key) is corrupted on function entry.

image

mratsim commented 4 years ago

Adding some debug shows that it's not the calling convention

proc `$`*(a: BIG_384): string
proc mul*(a: var ECP_BLS381, b: BIG_384) {.inline.} =
  ## Multiply point ``a`` by big integer ``b``.
  {.noSideEffect.}:
    debugEcho "common.mul b: ", $b
  ECP_BLS381_mul(addr a, b)

image

mratsim commented 4 years ago

So the garbage at the beginning may be hidden due to toHex(BIG_384) preprocessing

image

mratsim commented 4 years ago

Replacing


iterator validatorKeys*(conf: BeaconNodeConf): ValidatorPrivKey =
  for validatorKeyFile in conf.validators:
    try:
      yield validatorKeyFile.load
    except CatchableError as err:
      warn "Failed to load validator private key",
        file = validatorKeyFile.string, err = err.msg

  for kind, file in walkDir(conf.localValidatorsDir):
    if kind in {pcFile, pcLinkToFile} and
        cmpIgnoreCase(".privkey", splitFile(file).ext) == 0:
      try:
        yield ValidatorPrivKey.init(readFile(file).string)
      except CatchableError as err:
        warn "Failed to load a validator private key", file, err = err.msg

by

iterator validatorKeys*(conf: BeaconNodeConf): ValidatorPrivKey =
  for validatorKeyFile in conf.validators:
    try:
      yield validatorKeyFile.load
    except CatchableError as err:
      warn "Failed to load validator private key",
        file = validatorKeyFile.string, err = err.msg

  for kind, file in walkDir(conf.localValidatorsDir):
    if kind in {pcFile, pcLinkToFile} and
        cmpIgnoreCase(".privkey", splitFile(file).ext) == 0:
      try:
        let privkey = ValidatorPrivKey.init(readFile(file).string)
        debugEcho "iter: ", cast[array[7, uint64]](privkey)
      except CatchableError as err:
        warn "Failed to load a validator private key", file, err = err.msg

in https://github.com/status-im/nim-beacon-chain/blob/c205e32ed9e5db95977e08d7b3318fbc9abf98de/beacon_chain/conf.nim#L272-L286

solves the issue

mratsim commented 4 years ago

fromBytes assumed that the output buffer parameter was zero-initialized.

Existing data was properly overwritten if the input bytes/string was lengthy enough. But if it was too short, only part of limbs were overwritten

This is fixed in #44, calling fromBytes now zeroInit the buffer.