aboutsummaryrefslogtreecommitdiff
path: root/frozen_deps/ecdsa/test_malformed_sigs.py
blob: 8e1b611d1f78c5dbbc8651feb34525745bbc4927 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
from __future__ import with_statement, division

import hashlib

try:
    from hashlib import algorithms_available
except ImportError:  # pragma: no cover
    algorithms_available = [
        "md5",
        "sha1",
        "sha224",
        "sha256",
        "sha384",
        "sha512",
    ]
# skip algorithms broken by change to OpenSSL 3.0 and early versions
# of hashlib that list algorithms that require the legacy provider to work
# https://bugs.python.org/issue38820
algorithms_available = [
    i
    for i in algorithms_available
    if i not in ("mdc2", "md2", "md4", "whirlpool", "ripemd160")
]
from functools import partial
import pytest
import sys
import hypothesis.strategies as st
from hypothesis import note, assume, given, settings, example

from .keys import SigningKey
from .keys import BadSignatureError
from .util import sigencode_der, sigencode_string
from .util import sigdecode_der, sigdecode_string
from .curves import curves
from .der import (
    encode_integer,
    encode_bitstring,
    encode_octet_string,
    encode_oid,
    encode_sequence,
    encode_constructed,
)
from .ellipticcurve import CurveEdTw


example_data = b"some data to sign"
"""Since the data is hashed for processing, really any string will do."""


hash_and_size = [
    (name, hashlib.new(name).digest_size) for name in algorithms_available
]
"""Pairs of hash names and their output sizes.
Needed for pairing with curves as we don't support hashes
bigger than order sizes of curves."""


keys_and_sigs = []
"""Name of the curve+hash combination, VerifyingKey and DER signature."""


# for hypothesis strategy shrinking we want smallest curves and hashes first
for curve in sorted(curves, key=lambda x: x.baselen):
    for hash_alg in [
        name
        for name, size in sorted(hash_and_size, key=lambda x: x[1])
        if 0 < size <= curve.baselen
    ]:
        sk = SigningKey.generate(
            curve, hashfunc=partial(hashlib.new, hash_alg)
        )

        keys_and_sigs.append(
            (
                "{0} {1}".format(curve, hash_alg),
                sk.verifying_key,
                sk.sign(example_data, sigencode=sigencode_der),
            )
        )


# first make sure that the signatures can be verified
@pytest.mark.parametrize(
    "verifying_key,signature",
    [pytest.param(vk, sig, id=name) for name, vk, sig in keys_and_sigs],
)
def test_signatures(verifying_key, signature):
    assert verifying_key.verify(
        signature, example_data, sigdecode=sigdecode_der
    )


@st.composite
def st_fuzzed_sig(draw, keys_and_sigs):
    """
    Hypothesis strategy that generates pairs of VerifyingKey and malformed
    signatures created by fuzzing of a valid signature.
    """
    name, verifying_key, old_sig = draw(st.sampled_from(keys_and_sigs))
    note("Configuration: {0}".format(name))

    sig = bytearray(old_sig)

    # decide which bytes should be removed
    to_remove = draw(
        st.lists(st.integers(min_value=0, max_value=len(sig) - 1), unique=True)
    )
    to_remove.sort()
    for i in reversed(to_remove):
        del sig[i]
    note("Remove bytes: {0}".format(to_remove))

    # decide which bytes of the original signature should be changed
    if sig:  # pragma: no branch
        xors = draw(
            st.dictionaries(
                st.integers(min_value=0, max_value=len(sig) - 1),
                st.integers(min_value=1, max_value=255),
            )
        )
        for i, val in xors.items():
            sig[i] ^= val
        note("xors: {0}".format(xors))

    # decide where new data should be inserted
    insert_pos = draw(st.integers(min_value=0, max_value=len(sig)))
    # NIST521p signature is about 140 bytes long, test slightly longer
    insert_data = draw(st.binary(max_size=256))

    sig = sig[:insert_pos] + insert_data + sig[insert_pos:]
    note(
        "Inserted at position {0} bytes: {1!r}".format(insert_pos, insert_data)
    )

    sig = bytes(sig)
    # make sure that there was performed at least one mutation on the data
    assume(to_remove or xors or insert_data)
    # and that the mutations didn't cancel each-other out
    assume(sig != old_sig)

    return verifying_key, sig


params = {}
# not supported in hypothesis 2.0.0
if sys.version_info >= (2, 7):  # pragma: no branch
    from hypothesis import HealthCheck

    # deadline=5s because NIST521p are slow to verify
    params["deadline"] = 5000
    params["suppress_health_check"] = [
        HealthCheck.data_too_large,
        HealthCheck.filter_too_much,
        HealthCheck.too_slow,
    ]

slow_params = dict(params)
slow_params["max_examples"] = 10


@settings(**params)
@given(st_fuzzed_sig(keys_and_sigs))
def test_fuzzed_der_signatures(args):
    verifying_key, sig = args

    with pytest.raises(BadSignatureError):
        verifying_key.verify(sig, example_data, sigdecode=sigdecode_der)


@st.composite
def st_random_der_ecdsa_sig_value(draw):
    """
    Hypothesis strategy for selecting random values and encoding them
    to ECDSA-Sig-Value object::

        ECDSA-Sig-Value ::= SEQUENCE {
            r INTEGER,
            s INTEGER
        }
    """
    name, verifying_key, _ = draw(st.sampled_from(keys_and_sigs))
    note("Configuration: {0}".format(name))
    order = int(verifying_key.curve.order)

    # the encode_integer doesn't support negative numbers, would be nice
    # to generate them too, but we have coverage for remove_integer()
    # verifying that it doesn't accept them, so meh.
    # Test all numbers around the ones that can show up (around order)
    # way smaller and slightly bigger
    r = draw(
        st.integers(min_value=0, max_value=order << 4)
        | st.integers(min_value=order >> 2, max_value=order + 1)
    )
    s = draw(
        st.integers(min_value=0, max_value=order << 4)
        | st.integers(min_value=order >> 2, max_value=order + 1)
    )

    sig = encode_sequence(encode_integer(r), encode_integer(s))

    return verifying_key, sig


@settings(**slow_params)
@given(st_random_der_ecdsa_sig_value())
def test_random_der_ecdsa_sig_value(params):
    """
    Check if random values encoded in ECDSA-Sig-Value structure are rejected
    as signature.
    """
    verifying_key, sig = params

    with pytest.raises(BadSignatureError):
        verifying_key.verify(sig, example_data, sigdecode=sigdecode_der)


def st_der_integer(*args, **kwargs):
    """
    Hypothesis strategy that returns a random positive integer as DER
    INTEGER.
    Parameters are passed to hypothesis.strategy.integer.
    """
    if "min_value" not in kwargs:  # pragma: no branch
        kwargs["min_value"] = 0
    return st.builds(encode_integer, st.integers(*args, **kwargs))


@st.composite
def st_der_bit_string(draw, *args, **kwargs):
    """
    Hypothesis strategy that returns a random DER BIT STRING.
    Parameters are passed to hypothesis.strategy.binary.
    """
    data = draw(st.binary(*args, **kwargs))
    if data:
        unused = draw(st.integers(min_value=0, max_value=7))
        data = bytearray(data)
        data[-1] &= -(2**unused)
        data = bytes(data)
    else:
        unused = 0
    return encode_bitstring(data, unused)


def st_der_octet_string(*args, **kwargs):
    """
    Hypothesis strategy that returns a random DER OCTET STRING object.
    Parameters are passed to hypothesis.strategy.binary
    """
    return st.builds(encode_octet_string, st.binary(*args, **kwargs))


def st_der_null():
    """
    Hypothesis strategy that returns DER NULL object.
    """
    return st.just(b"\x05\x00")


@st.composite
def st_der_oid(draw):
    """
    Hypothesis strategy that returns DER OBJECT IDENTIFIER objects.
    """
    first = draw(st.integers(min_value=0, max_value=2))
    if first < 2:
        second = draw(st.integers(min_value=0, max_value=39))
    else:
        second = draw(st.integers(min_value=0, max_value=2**512))
    rest = draw(
        st.lists(st.integers(min_value=0, max_value=2**512), max_size=50)
    )
    return encode_oid(first, second, *rest)


def st_der():
    """
    Hypothesis strategy that returns random DER structures.

    A valid DER structure is any primitive object, an octet encoding
    of a valid DER structure, sequence of valid DER objects or a constructed
    encoding of any of the above.
    """
    return st.recursive(
        st.just(b"")
        | st_der_integer(max_value=2**4096)
        | st_der_bit_string(max_size=1024**2)
        | st_der_octet_string(max_size=1024**2)
        | st_der_null()
        | st_der_oid(),
        lambda children: st.builds(
            lambda x: encode_octet_string(x), st.one_of(children)
        )
        | st.builds(lambda x: encode_bitstring(x, 0), st.one_of(children))
        | st.builds(
            lambda x: encode_sequence(*x), st.lists(children, max_size=200)
        )
        | st.builds(
            lambda tag, x: encode_constructed(tag, x),
            st.integers(min_value=0, max_value=0x3F),
            st.one_of(children),
        ),
        max_leaves=40,
    )


@settings(**params)
@given(st.sampled_from(keys_and_sigs), st_der())
def test_random_der_as_signature(params, der):
    """Check if random DER structures are rejected as signature"""
    name, verifying_key, _ = params

    with pytest.raises(BadSignatureError):
        verifying_key.verify(der, example_data, sigdecode=sigdecode_der)


@settings(**params)
@given(st.sampled_from(keys_and_sigs), st.binary(max_size=1024**2))
@example(
    keys_and_sigs[0], encode_sequence(encode_integer(0), encode_integer(0))
)
@example(
    keys_and_sigs[0],
    encode_sequence(encode_integer(1), encode_integer(1)) + b"\x00",
)
@example(keys_and_sigs[0], encode_sequence(*[encode_integer(1)] * 3))
def test_random_bytes_as_signature(params, der):
    """Check if random bytes are rejected as signature"""
    name, verifying_key, _ = params

    with pytest.raises(BadSignatureError):
        verifying_key.verify(der, example_data, sigdecode=sigdecode_der)


keys_and_string_sigs = [
    (
        name,
        verifying_key,
        sigencode_string(
            *sigdecode_der(sig, verifying_key.curve.order),
            order=verifying_key.curve.order
        ),
    )
    for name, verifying_key, sig in keys_and_sigs
    if not isinstance(verifying_key.curve.curve, CurveEdTw)
]
"""
Name of the curve+hash combination, VerifyingKey and signature as a
byte string.
"""


keys_and_string_sigs += [
    (
        name,
        verifying_key,
        sig,
    )
    for name, verifying_key, sig in keys_and_sigs
    if isinstance(verifying_key.curve.curve, CurveEdTw)
]


@settings(**params)
@given(st_fuzzed_sig(keys_and_string_sigs))
def test_fuzzed_string_signatures(params):
    verifying_key, sig = params

    with pytest.raises(BadSignatureError):
        verifying_key.verify(sig, example_data, sigdecode=sigdecode_string)