jvdsn/crypto-attacks

Python implementations of cryptographic attacks and utilities.

crypto-attacks's Issues

coppersmith timings vary a lot

Hey it's me from the email again.
I've been trying to solve corrupt-key-2 from PicoGym

I'm using an example I generated myself, I added the code below to the end of the coppersmith.py file

exa_N  = 174689501556974852774692456662282428651334567739483151394730366472723757343603695946018382897568356669603128108034723257753348635879786275267108581170688382291283798632863388202044928301928828912510733489700352690675873162118680451826827914903826567505877313658436202501645891375370591464209179799149746598607
exa_p = "ff5a380b8894d65327b9ef6af157b365e8bb1cff346e98a7c5c7f022123f890f7324c6b096c4516e769fd6e6ee8fe88fd901b33d9fd1e717ed777ee137d51175"
exapm = "ff5a380b8894d65327b9ef6af157b3??????????346e98a7c5c7f022123f????????c6b096c4516e769fd6e6ee8fe88fd901b33d9fd1e717ed????????d51175"
print(factorize_p(exa_N, PartialInteger.from_hex_be(exapm), m=5, t=1))

My question is why at times these lines seem to get executed in less than half a minute, and other times they take way too long for me to measure?
I'm asking this because I'm trying to bruteforce bits of the prime, but I can't figure out which bits should I bruteforce for most efficiency
These are the actual values I have (the ones above are just for testing):

orig_p= "fe8984407b0816cc28e5ccc6bb7379??????????ca3806dd2cfdfc8d616b????????6109a4dbe3876b8d1b8adc9175dfba0e1ef318801648d6??????????a05b"
orig_N =  0xc20d4f0792f162e3f3486f47c2c5b05696ba5c81ec09f5386bf741b7289b85e2d744559825a23b0ae094da214f3158344e5d5ba86fb1ecd1f40c8682a7bee55021eba772e23793001a38b9cccbfdc1d9316cccc3b79acd045c512b44e0f3697383958113a280791e17c23fe80fa38099e4907f70f4d228285aac69ed2d3bcf99

Short Nonces in ECDSA

Hello @jvdsn I saw your work on GitHub and decided to write to you as I have questions.

When creating ECDSA, it happens that some devices generate short Nonce.
Approximately 2 ^ 243 - 2 ^ 244

Accordingly, if Nonces is short, then it must contain null at the beginning.
That is, the first 3 bits of the Nonce contain a beginning null.

Given the known signature values [R, S, H (e)], can we define and calculate if the Nonce is short?

Is there a way to find out information about the first 3 bits of Nonces?

something wrong when I run the code:rsa/wiener_attack_common_rsa_prime.py

IndexError: list index out of range

n = 253784908428481171520644795825628119823506176672683456544539675613895749357067944465796492899363087465652749951069021248729871498716450122759675266109104893465718371075137027806815473672093804600537277140261127375373193053173163711234309619016940818893190549811778822641165586070952778825226669497115448984409
e = 31406775715899560162787869974700016947595840438708247549520794775013609818293759112173738791912355029131497095419469938722402909767606953171285102663874040755958087885460234337741136082351825063419747360169129165
c = 97724073843199563126299138557100062208119309614175354104566795999878855851589393774478499956448658027850289531621583268783154684298592331328032682316868391120285515076911892737051842116394165423670275422243894220422196193336551382986699759756232962573336291032572968060586136317901595414796229127047082707519
delta = 0.132
print(delta)
p, q, d = attack(n, e, delta)
print(long_to_bytes(pow(c, d, n)))

shared.ecc.generate_with_order speed up

same problem: J08nY/ecgen#23
pari.qfbsolve(pari.Qfb(1, 0, -D), 4 * m, 1) is slow because pari try to factor m every time.
our solution:

m = Integer(sys.argv[1])
out = subprocess.check_output(['./yafu'], input=f'factor({m})'.encode())
for p in [int(a.split(b' = ')[1]) for a in out.splitlines() if b' = ' in a and a[0] == b'P'[0]]:
    if p > 1000:
        pari.addprimes(p)

seems we can replace yafu with default sage factor(m)

Generate Anomalous Curve with Given order

I was wondering if it is possible to extend the the function generate_anomalous_q to generate curves with more types of prime numbers, as mentioned in this paper for the case (Case hD ≥ 2.)

(https://doi.org/10.1016/j.ipl.2004.11.008)

Edit:
in this file shared/ecc.py you mentioned you'll implement "Accelerating the CM method" by Sutherland. Would you be able to do that? That might help to generate elliptic curve with a given order

how to use "Branch and prune for the case with p, q, and d bits known"?

how to use "Branch and prune for the case with p, q, and d bits known"?

adding aes cpa and dpa attacks

rewrited exploit for cpa from https://wiki.newae.com/V4:Tutorial_B6_Breaking_AES_(Manual_CPA_Attack) :

import numpy as np
import logging

HW = [bin(n).count("1") for n in range(0,256)]

sbox=(
0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76,
0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0,
0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15,
0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75,
0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84,
0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf,
0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8,
0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2,
0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73,
0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb,
0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79,
0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08,
0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a,
0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e,
0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf,
0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16)

def intermediate(pt, keyguess):
    return sbox[pt ^ keyguess]


def attack(pt: list[np.array], traces: list[np.array]): # without np.array will be very slow
    numtraces = np.shape(traces)[0]-1
    numpoint = np.shape(traces)[1]
    
    
    #Set 16 to something lower (like 1) to only go through a single subkey
    bestguess = [0]*16
    for bnum in range(0, 16):
        cpaoutput = [0]*256
        maxcpa = [0]*256
        for kguess in range(0, 256):
            logging.info("Subkey %2d, hyp = %02x: "%(bnum, kguess))
    
            sumnum = np.zeros(numpoint)
            sumden1 = np.zeros(numpoint)
            sumden2 = np.zeros(numpoint)
    
            hyp = np.zeros(numtraces)
            for tnum in range(0, numtraces):
                hyp[tnum] = HW[intermediate(pt[tnum][bnum], kguess)]
            meanh = np.mean(hyp, dtype=np.float64)
    
            meant = np.mean(traces, axis=0, dtype=np.float64)
    
            for tnum in range(0, numtraces):
                hdiff = (hyp[tnum] - meanh)
                tdiff = traces[tnum] - meant
    
                sumnum += hdiff*tdiff
                sumden1 += hdiff*hdiff 
                sumden2 += tdiff*tdiff
    
            cpaoutput[kguess] = sumnum / np.sqrt( sumden1 * sumden2 )
            maxcpa[kguess] = max(abs(cpaoutput[kguess]))
            logging.info(maxcpa[kguess])
    
        bestguess[bnum] = np.argmax(maxcpa)

    return bytes(bestguess)

how to use

hi i want to practice with your code , can u explain to me how can i use smart's attack on y^2=x^3+7 module P=61 while t=1 , for points Q=(30,44) and G=(9,2) ??

Any C/C++ implementation

Hey, first of all - sorry for writing in issues section and disturbing anyone but I have a question that haunts me. Your python implementation is great, but I wondering is there anython like that but on c/c++? Especially I'm searching for branch and prune algo for known random bits for p and q. It was very hard to find even your code, it's just algo description everywhere and not code. So, if you know anything about it, I would really appreciate.

TypeError in Example code rsa/boneh_durfee.py

Hi, thank you for your work!
Can you help me to run Example script from your Readme instructions?(https://github.com/jvdsn/crypto-attacks/blob/master/README.md)

I have error:

#######
INFO:root:Trying m = 1, t = 0...
DEBUG:root:Generating shifts...
DEBUG:root:Creating a lattice with 3 shifts (order = invlex, sort_shifts_reverse = False, sort_monomials_reverse = False)...
DEBUG:root:Reducing a 3 x 3 lattice...
DEBUG:root:Reconstructing polynomials (divide_original = True, modulus_bound = True, divide_gcd = True)...
DEBUG:root:Row 0 is too large, ignoring...
DEBUG:root:Row 1 is too large, ignoring...
DEBUG:root:Row 2 is too large, ignoring...
DEBUG:root:Reconstructed 0 polynomials
DEBUG:root:Computing pairwise gcds to find trivial roots...
DEBUG:root:Using Groebner basis method to find roots...
Traceback (most recent call last):
File "/crypto-attacks/attacks/rsa/boneh_durfee.py", line 94, in
p, q = attack(N, e, p_bits, delta=delta)
TypeError: cannot unpack non-iterable NoneType object
#######

What parameter(s) is wrong?

A added example of your code to /attacks/rsa/boneh_durfee.py:

#######
import logging

Some logging so we can see what's happening.

logging.basicConfig(level=logging.DEBUG)

N = 88320836926176610260238895174120738360949322009576866758081671082752401596826820274141832913391890604999466444724537056453777218596634375604879123818123658076245218807184443147162102569631427096787406420042132112746340310992380094474893565028303466135529032341382899333117011402408049370805729286122880037249
e = 36224751658507610673165956970793195381480143363550601971796688201449789736497322700382657163240771111376677180786660893671085854060092736865293791299460933460067267613023891500397200389824179925263846148644777638774319680682025117466596019474987378275216579013846855328009375540444176771945272078755317168511
p_bits = 512
delta = 0.26

p, q = attack(N, e, p_bits, delta=delta)
assert p * q == N
print(f"Found p = {p} and q = {q}")
#######

Frey ruck attack test

Hi, I need your help.
Please, can you say me how i can to get my own numbers in test example?
How I can generate or calculate P, R and l points?
Is it possible?

For example, we have a function:
def test_frey_ruck_attack(self):
p = 23305425500899
a = 13079575536215
b = 951241857177
l = 709658
E = EllipticCurve(GF(p), [a, b])
P = E(17662927853004, 1766549410280)
R = E(2072411881257, 5560421985272)
l_ = frey_ruck_attack.attack(P, R)
self.assertIsInstance(l_, int)
self.assertEqual(l, l_)

But I don't understand what is:
l = 709658
P = E(17662927853004, 1766549410280)
R = E(2072411881257, 5560421985272)
How we got that numbers?

I think that these numbers are Px, Py, Rx, Ry, l

What is P in this example, is this a public key if we talk about Bitcoin or base point?

Gx=79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

And what is l, private key, nonce or other parameter?

memory usage in hencel lift

https://github.com/jvdsn/crypto-attacks/blob/master/shared/hensel.py#L33
FIX:

#        roots = list(range(p))
        roots = range(p)

because list(range(big_p)) will use so much memory

A faster function to solve the DLP question in ecc's singular_curve.py

In some tests, using "return v.log(u)" instead of "return int(discrete_log(v, u))" is more efficient.
What are the differences between the two functions?
Thanks.

SyntaxError: invalid syntax

tell me what am I doing wrong?

p_ = (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
r_ = (0xd11a650e0618d0901466dc22a1014e858c06e95de5077051af6e92cf9900ef71,0x677fc5dce98a343d3ab0156faf6eadd4607b630c0028efb6b5da17e1d1931cc0)
res = attack(p_)
print(res)

AMM method function rth_roots() get same roots

When I tried to use this function to solve a CTF challenge, I found this problem.

from sage.all import *
from CryptoAttack.shared import rth_roots

c = 7267288183214469410349447052665186833632058119533973432573869246434984462336560480880459677870106195135869371300420762693116774837763418518542884912967719
e = 21
q = 9908484735485245740582755998843475068910570989512225739800304203500256711207262150930812622460031920899674919818007279858208368349928684334780223996774347
print(list(rth_roots(GF(q), c, e)))

I got this output

[5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446]

all roots is 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446.

but when I made this change

def roots_of_unity(ring, l, r):
    """
    Generates r-th roots of unity in a ring, with r | l.
    :param ring: the ring, with order n
    :param l: the Carmichael lambda of n
    :param r: r
    :return: a generator generating the roots of unity
    """
    assert l % r == 0, "r should divide l"

    x = ring(3)
    while x ** l != 1:
        x += 1
    print(x)
    g = x ** (l // r)
    for i in range(r):
        yield int(g ** i)

I replace the initial value of x with 3, I got the right solution

[5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 280144707245011294640488506115562281365276356125932100207397393027860909029413220156776010197352605708589655905445419432143442931322397721593647968474277, 7430474113276965115422561010012825056649819720622305012119305319337399559413055056545816300802245496064549287797757557077547908297143373105085421303274867, 4563675787323427286374907245468529995244053214707683042368598801135429713200620060437513752829145989678698319665342340325183439671079059924144916004756970, 2798072739863399815101890848589737393172952179316532589269644554919015010733862014492230886774517981425049058508156951568239808827156512588164729805156879, 9391573497164348797642157544159683077847387626417455197573630359125733460335703475872083705628619684219006073476648010518321422909263199325412678307023692, 154110187494616397671066227097770386558859787802617565773755349387989231317636267478296013662932004413507040541332089184010995557074142252157423736369910, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 280144707245011294640488506115562281365276356125932100207397393027860909029413220156776010197352605708589655905445419432143442931322397721593647968474277, 7430474113276965115422561010012825056649819720622305012119305319337399559413055056545816300802245496064549287797757557077547908297143373105085421303274867, 4563675787323427286374907245468529995244053214707683042368598801135429713200620060437513752829145989678698319665342340325183439671079059924144916004756970, 2798072739863399815101890848589737393172952179316532589269644554919015010733862014492230886774517981425049058508156951568239808827156512588164729805156879, 9391573497164348797642157544159683077847387626417455197573630359125733460335703475872083705628619684219006073476648010518321422909263199325412678307023692, 154110187494616397671066227097770386558859787802617565773755349387989231317636267478296013662932004413507040541332089184010995557074142252157423736369910, 5107403174087968514895196615086317015893364083544151712088580833567342249591496357809721197485282001189625323559339471469178086856747368087781854865266446, 280144707245011294640488506115562281365276356125932100207397393027860909029413220156776010197352605708589655905445419432143442931322397721593647968474277, 7430474113276965115422561010012825056649819720622305012119305319337399559413055056545816300802245496064549287797757557077547908297143373105085421303274867, 4563675787323427286374907245468529995244053214707683042368598801135429713200620060437513752829145989678698319665342340325183439671079059924144916004756970, 2798072739863399815101890848589737393172952179316532589269644554919015010733862014492230886774517981425049058508156951568239808827156512588164729805156879, 9391573497164348797642157544159683077847387626417455197573630359125733460335703475872083705628619684219006073476648010518321422909263199325412678307023692, 154110187494616397671066227097770386558859787802617565773755349387989231317636267478296013662932004413507040541332089184010995557074142252157423736369910]

Extended partial key exposure attacks on RSA: Improvement up to full size decryption exponents

Could you please add support for the attack in the 2020 paper:

"Extended partial key exposure attacks on RSA: Improvement up to full size decryption exponents"
Kaichi Suzuki, Atsushi Takayasu, Noboru Kunihiro

Thank you