Non-Recoverable Signatures

[jannikluhn]

What was wrong?

57

How was it fixed?

Signatures without v values are implemented in a new class called NonRecoverableSignature. Some of the shared functionality with the existing Signature class has been moved to BaseSignature. Creating non recoverable signatures is handled by new backend methods. Verifying them uses the existing ones, which have been updated to accept all BaseSignatures (i.e. not recover and compare, but direct verification).

Coincurve uses a DER format to encode/decode these signatures. As it is quite complicated I added a new dependency: asn1tools which looks relatively well maintained.

This should probably be merged after #56, then I can use the improved validation functions from there.

Cute Animal Picture

[carver]

Any other asn1 tools that you considered? pyasn1 seems to be much more widely used: https://github.com/etingof/pyasn1/network/dependents (37k dependent projects)

vs https://github.com/eerimoq/asn1tools/network/dependents (3 dependent projects?)

Also, pyasn1 doesn't have any sub-dependencies, where asn1tools has a few.

Normally, I'm relatively liberal with dependencies, but since this is an absolutely security-critical library, it would be nice to minimize the dependency risk.

[carver]

asn1tools has another issue: there are some dependency conflicts with prompt_toolkit that ipython also depends on. It might be possible to manually resolve it by figuring out which ipython that trinity needs to specify, but I'd rather not go down that rabbit hole.

[jannikluhn]

Nice, I didn't know of the dependency graph feature. Now that I've seen it, I agree that pyasn1 is the much better choice. Will swap them.

[pipermerriam]

Can I ask whether it is possible to do this without the added dependency? Would it be possible to do it using pure coincurve and then use asn1 in our tests to verify correctness?

Sent from ProtonMail mobile

-------- Original Message -------- On May 23, 2019, 9:23 AM, jannikluhn wrote:

Nice, I didn't know of the dependency graph feature. Now that I've seen it, I agree that pyasn1 is the much better choice. Will swap them.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.

[jannikluhn]

I didn't dare to try as DER encoding is relatively complicated even if implemented just for the signature object. It's ancient and weird, in some cases even requires checking individual bit values. Here's documentation of the parts that would be relevant to us: Sequence and Integer.

So I think using an external library is the better way to go. But if you feel strongly about this, I can also try to reimplement it here.

[carver]

Looks pretty doable, since we know a lot about the specific spec and the input range. two_int_sequence_encoder appears to be a working encoder, below:

import pytest

import asn1tools
from eth_utils import (
    apply_to_return_value,
    int_to_big_endian,
)
from hypothesis import (
    example,
    settings,
    strategies as st,
    given,
)

ASN1_ECDSA_SPEC_STRING = """\
ECDSASpec DEFINITIONS ::= BEGIN
      ECDSASignature ::= SEQUENCE {
         r   INTEGER,
         s   INTEGER
     }
END
"""
ASN1_SPEC = asn1tools.compile_string(ASN1_ECDSA_SPEC_STRING, "der")

@apply_to_return_value(bytes)
def int_encoder(primitive):
    """
    Only handles 32-byte positive ints
    """
    # Integer tag
    yield 0x02

    encoded = int_to_big_endian(primitive)
    if encoded[0] >= 128:
        # Indicate that integer is positive, if the first bit is 1
        # we need to disambiguate it from a 2's complement negative number
        yield len(encoded) + 1 
        yield 0x00
    else: 
        yield len(encoded) 

    yield from encoded

@apply_to_return_value(bytes)
def two_int_sequence_encoder(int1, int2):
    # Sequence tag
    yield 0x30

    encoded1 = int_encoder(int1)
    encoded2 = int_encoder(int2)

    # Sequence length
    yield len(encoded1) + len(encoded2)

    yield from encoded1
    yield from encoded2

MAX_32_BYTE_INT = 256 ** 32 - 1 
@given(
    st.integers(min_value=0, max_value=MAX_32_BYTE_INT),
    st.integers(min_value=0, max_value=MAX_32_BYTE_INT),
)
@example(0, 0)
@example(MAX_32_BYTE_INT, MAX_32_BYTE_INT)
@example(MAX_32_BYTE_INT // 2, MAX_32_BYTE_INT // 2)
@example(MAX_32_BYTE_INT // 2 + 1, MAX_32_BYTE_INT // 2 + 1)
@settings(max_examples=1000)
def test_hand_coded_asn1(r, s):
    encoded = two_int_sequence_encoder(r, s)
    expected = ASN1_SPEC.encode("ECDSASignature", {"r": r, "s": s})
    assert encoded == bytes(expected) 

(though we should re-write the tests to work against pyasn1)

[carver]

If you like, I can open a separate PR to add the internal asn1 util, since it looks like I'm at least 40% of the way there (need to add the decoder, and to switch to the other library)

[pipermerriam]

Maybe worth having both so we can compare.

Sent from ProtonMail mobile

-------- Original Message -------- On May 24, 2019, 7:07 PM, Jason Carver wrote:

If you like, I can open a separate PR to add the internal asn1 util, since it looks like I'm at least 40% of the way there (need to add the decoder, and to switch to the other library)

— You are receiving this because you commented. Reply to this email directly, view it on GitHub, or mute the thread.

[carver]

Okay, the decoder is also straightforward:

import pytest

import asn1tools
from eth_utils import (
    apply_to_return_value,
    big_endian_to_int, 
    int_to_big_endian,
)
from hypothesis import (
    example,
    settings,
    strategies as st,
    given,
)

ASN1_ECDSA_SPEC_STRING = """\
ECDSASpec DEFINITIONS ::= BEGIN
      ECDSASignature ::= SEQUENCE {
         r   INTEGER,
         s   INTEGER
     }
END
"""
ASN1_SPEC = asn1tools.compile_string(ASN1_ECDSA_SPEC_STRING, "der")

@apply_to_return_value(bytes)
def int_encoder(primitive):
    """
    Only handles 32-byte (yes *byte*) positive ints
    """
    # Integer tag
    yield 0x02

    encoded = int_to_big_endian(primitive)
    if encoded[0] >= 128:
        # Indicate that integer is positive (it always is, but doesn't always need the flag)
        yield len(encoded) + 1
        yield 0x00
    else:
        yield len(encoded)

    yield from encoded

@apply_to_return_value(bytes)
def two_int_sequence_encoder(int1, int2):
    # Sequence tag
    yield 0x30

    encoded1 = int_encoder(int1)
    encoded2 = int_encoder(int2)

    # Sequence length
    yield len(encoded1) + len(encoded2)

    yield from encoded1
    yield from encoded2

def decode_int(encoded):
    assert encoded[0] == 0x02

    length = encoded[1] 
    # to_int can handle leading zeros
    decoded_int = big_endian_to_int(encoded[2:2 + length])

    return decoded_int, encoded[2 + length:]

def two_int_sequence_decoder(encoded):
    assert encoded[0] == 0x30

    # skip sequence length 
    int1, rest = decode_int(encoded[2:]) 
    int2, empty = decode_int(rest)

    assert len(empty) == 0 
    return int1, int2 

MAX_32_BYTE_INT = 256 ** 32 - 1
@given(
    st.integers(min_value=0, max_value=MAX_32_BYTE_INT),
    st.integers(min_value=0, max_value=MAX_32_BYTE_INT),
)
@example(0, 0)
@example(MAX_32_BYTE_INT, MAX_32_BYTE_INT)
@example(MAX_32_BYTE_INT // 2, MAX_32_BYTE_INT // 2)
@example(MAX_32_BYTE_INT // 2 + 1, MAX_32_BYTE_INT // 2 + 1)
@settings(max_examples=1000)
def test_hand_coded_asn1(r, s):
    encoded = two_int_sequence_encoder(r, s)
    expected = ASN1_SPEC.encode("ECDSASignature", {"r": r, "s": s})
    assert encoded == bytes(expected)

MAX_32_BYTE_INT = 256 ** 32 - 1
@given(
    st.integers(min_value=0, max_value=MAX_32_BYTE_INT),
    st.integers(min_value=0, max_value=MAX_32_BYTE_INT),
)
@example(0, 0)
@example(MAX_32_BYTE_INT, MAX_32_BYTE_INT)
@example(MAX_32_BYTE_INT // 2, MAX_32_BYTE_INT // 2)
@example(MAX_32_BYTE_INT // 2 + 1, MAX_32_BYTE_INT // 2 + 1)
@settings(max_examples=1000)
def test_asn1tools_encode_handrolled_decode(r, s):
    encoded = ASN1_SPEC.encode("ECDSASignature", {"r": r, "s": s})
    end_r, end_s = two_int_sequence_decoder(encoded) 
    assert (end_r, end_s) == (r, s)

If I don't hear back, I'll pick this up on Tuesday into its own PR.

[jannikluhn]

Nice, thank you! That's indeed more straightforward than I expected. I've started to integrate your code, but now that you've written the decoder as well I think it would fit better in its own PR.

[jannikluhn]

Removed the asn1tools dependency, in anticipation of @carver's PR. I just guessed an interface from the snippet above for now, but don't mind updating it if it turns out to be different.

[carver]

Ok, can rebase on #60 now

[jannikluhn]

I've updated this PR to use new DER codec, cleaned up the commit history a little, and removed some direction duplication in the tests that carver already pointed out but slipped through for some reason. So it's ready from my side, could I get a final review so that we can merge this please?

[pipermerriam]

@jannikluhn let me know when you're read for us to click merge (or you can if you have permission but I don't think you do)

[jannikluhn]

Thanks, you're right, I don't have permission. It's ready from my side, as long as you're happy with the name validate_signature_r_or_s (couldn't come up with something better, but at least it's expressive).

Also, would be great if you could make a new release so that we can use it in Trinity.

[pipermerriam]

gonna wait for @carver to second this, then I'll merge and cut you a release.

[pipermerriam]

@jannikluhn available as v0.3.0