Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Stack corruption due to ECP_mul temporary #43

Closed
mratsim opened this issue Mar 12, 2020 · 5 comments
Closed

Stack corruption due to ECP_mul temporary #43

mratsim opened this issue Mar 12, 2020 · 5 comments

Comments

@mratsim
Copy link
Contributor

mratsim commented Mar 12, 2020

A followup on #40 and another debugging session on status-im/nimbus-eth2#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
Copy link
Contributor Author

mratsim commented Mar 12, 2020

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
Copy link
Contributor Author

mratsim commented Mar 12, 2020

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
Copy link
Contributor Author

mratsim commented Mar 12, 2020

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

image

@mratsim
Copy link
Contributor Author

mratsim commented Mar 12, 2020

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
Copy link
Contributor Author

mratsim commented Mar 12, 2020

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.

@mratsim mratsim closed this as completed Mar 12, 2020
mratsim added a commit to status-im/nimbus-eth2 that referenced this issue Mar 12, 2020
tersec pushed a commit to status-im/nimbus-eth2 that referenced this issue Mar 13, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant