search

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 on keypair generation #40

Closed mratsim closed 4 years ago

mratsim commented 4 years ago

The stack can be corrupted on key-pair generation.

For some reason this does not happen when generated in a loop, for example

import blscurve, nimcrypto

proc main() =

  for i in 0 ..< 100:
    echo "iteration ", i, ":"
    var ikm: array[32, byte]

    let written = randomBytes(ikm)
    doAssert written >= 32, "Key generation failure"

    var secKey: SecretKey
    var pubKey: PublicKey

    let ok = keygen(ikm, pubkey, seckey)

    doAssert ok
    echo "  seckey: ", seckey.toHex()
    echo "  pubkey: ", pubkey.toHex()

main()

But it happens when generated in global arrays (even on the heap) like in PR https://github.com/status-im/nim-beacon-chain/pull/780 unless it has to do with object variants?

import
  # Specs
  ../../beacon_chain/spec/[datatypes, crypto]

# this is being indexed inside "mock_deposits.nim" by a value up to `validatorCount`
# which is `num_validators` which is `MIN_GENESIS_ACTIVE_VALIDATOR_COUNT`
proc genMockPrivKeys(privkeys: var array[MIN_GENESIS_ACTIVE_VALIDATOR_COUNT, ValidatorPrivKey]) =
  for i in 0 ..< privkeys.len:
    let pair = newKeyPair()
    privkeys[i] = pair.priv

proc genMockPubKeys(
       pubkeys: var array[MIN_GENESIS_ACTIVE_VALIDATOR_COUNT, ValidatorPubKey],
       privkeys: array[MIN_GENESIS_ACTIVE_VALIDATOR_COUNT, ValidatorPrivKey]
     ) =
  for i in 0 ..< privkeys.len:
    pubkeys[i] = pubkey(privkeys[i])

# TODO: Ref array necessary to use a proc to avoid stack smashing in ECP_BLS381_mul (see gdb)
var MockPrivKeys*: ref array[MIN_GENESIS_ACTIVE_VALIDATOR_COUNT, ValidatorPrivKey]
new MockPrivKeys
genMockPrivKeys(MockPrivKeys[])

var MockPubKeys*: ref array[MIN_GENESIS_ACTIVE_VALIDATOR_COUNT, ValidatorPubKey]
new MockPubKeys
genMockPubKeys(MockPubKeys[], MockPrivKeys[])

type MockKey = ValidatorPrivKey or ValidatorPubKey

template `[]`*[N: static int](a: array[N, MockKey], idx: ValidatorIndex): MockKey =
  a[idx.int]

when isMainModule:
  from blscurve import toHex

  echo "========================================"
  echo "Mock keys"
  for i in 0 ..< MIN_GENESIS_ACTIVE_VALIDATOR_COUNT:
    echo "  validator ", i
    echo "    seckey: ", MockPrivKeys[i].toHex()
    echo "    pubkey: ", MockPubKeys[i]

In Clang

This seems to manifest as a secret key that is bigger than the curve order: image

In GDB we crash soon after

image

mratsim commented 4 years ago

AddressSanitizer report on the openarray branch: https://github.com/status-im/nim-blscurve/commit/49bed1afa38a36948ebf063340ecf930d0507dcd

nim c --cc:clang --passC:-fsanitize=address --passL:"-fsanitize=address" --verbosity:0 --warnings:off --hints:off -r --outdir:build tests/mocking/mock_validator_keys.nim

You may need to add -lclang_rt.asan_dynamic-x86_64 to passL on WIndows

Note that seckey should be lesser than the CurveOrder so there is at least one error earlier than the stacktrace

keyGen:
  CURVE_Order: 0000000000000000000000000000000073eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
  seckey (mod): 7e65031cc69d8847cc1dab551b7b3b273167c64ccb50432062f3f06d59a8048f4d62360c7914c49a79b16f090b3f0a88
=================================================================
==185309==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fff8be89487 at pc 0x55d55600c801 bp 0x7fff8be889b0 sp 0x7fff8be889a8
WRITE of size 1 at 0x7fff8be89487 thread T0
    #0 0x55d55600c800 in ECP_BLS381_mul /home/beta/Programming/Status/nim-beacon-chain/vendor/nim-blscurve/blscurve/csources/64/ecp_BLS381.c:1105:13
    #1 0x55d5560b1dab in mul__8dasrHsBDivosc1xoLwN9aQcommon /home/beta/Programming/Status/nim-beacon-chain/vendor/nim-blscurve/blscurve/common.nim:297:2
    #2 0x55d5560b1dab in privToPub__SbUVL7n9atErGXu7gDCy72Q /home/beta/Programming/Status/nim-beacon-chain/vendor/nim-blscurve/blscurve/bls_signature_scheme.nim:97:2
    #3 0x55d5560b3455 in keyGen__k9aA4fW208vT3m9bROeHOvQQ /home/beta/Programming/Status/nim-beacon-chain/vendor/nim-blscurve/blscurve/bls_signature_scheme.nim:540:17
    #4 0x55d5560b4b8f in newKeyPair__WaRCyvULs0D775n9ckxybgA /home/beta/Programming/Status/nim-beacon-chain/beacon_chain/spec/crypto.nim:206:29
    #5 0x55d5560b8cde in genMockPrivKeys__eJmkvjU6oWGYzAhJKIXKTw /home/beta/Programming/Status/nim-beacon-chain/tests/mocking/mock_validator_keys.nim:19:12
    #6 0x55d5560b8cde in NimMainModule /home/beta/Programming/Status/nim-beacon-chain/tests/mocking/mock_validator_keys.nim:32:2
    #7 0x55d5560ba90a in NimMain /home/beta/.nimble/pkgs/serialization-0.1.0/serialization/errors.nim:56:2
    #8 0x55d5560ba90a in main /home/beta/.nimble/pkgs/serialization-0.1.0/serialization/errors.nim:63:2
    #9 0x7f469be4a022 in __libc_start_main (/usr/lib/libc.so.6+0x27022)
    #10 0x55d555f1618d in _start (/home/beta/Programming/Status/nim-beacon-chain/build/mock_validator_keys+0x2c18d)

Address 0x7fff8be89487 is located in stack of thread T0 at offset 2759 in frame
    #0 0x55d55600c12f 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:1105:13 in ECP_BLS381_mul
Shadow bytes around the buggy address:
  0x1000717c9240: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000717c9250: 00 00 00 00 f2 f2 f2 f2 f2 f2 f2 f2 f2 f2 f2 f2
  0x1000717c9260: f2 f2 f2 f2 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000717c9270: 00 00 00 00 00 00 00 00 00 00 00 00 f2 f2 f2 f2
  0x1000717c9280: f2 f2 f2 f2 00 00 00 00 00 00 00 00 00 00 00 00
=>0x1000717c9290:[07]f3 f3 f3 f3 f3 f3 f3 00 00 00 00 00 00 00 00
  0x1000717c92a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000717c92b0: 00 00 00 00 00 00 00 00 f1 f1 f1 f1 f8 f8 f8 f8
  0x1000717c92c0: f8 f2 f2 f2 f2 f2 00 00 00 00 00 f2 f2 f2 f2 f2
  0x1000717c92d0: 00 00 00 00 00 f2 f2 f2 f2 f2 f8 f8 f8 f8 f8 f8
  0x1000717c92e0: 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
==185309==ABORTING

The incriminated w on line 1061: https://github.com/status-im/nim-blscurve/blob/9a143350f107b9bbd8c4d9bb4807e3b470aa232b/blscurve/csources/64/ecp_BLS381.c#L1056-L1061

mratsim commented 4 years ago

For some reason Milagro cannot take the modulo of this

import blscurve/[milagro, common]

proc main() =

  var okm: BIG_384
  doAssert okm.fromHex"7e65031cc69d8847cc1dab551b7b3b273167c64ccb50432062f3f06d59a8048f4d62360c7914c49a79b16f090b3f0a88"

  debugEcho "CurveOrder: ", CURVE_Order.toHex()

  var seckey = okm
  BIG_384_mod(okm, CURVE_Order)

  echo "seckey: ", seckey

main()