Introdução

Implementações em Python de ataques criptográficos e utilitários.

Requisitos

• SageMath com Python 3.9
• PyCryptodome

Pode verificar a versão do Python do SageMath usando o seguinte comando:``` $ sage -python --version Python 3.9.0

Se a sua versão do Python do SageMath for anterior a 3.9.0, alguns recursos em alguns scripts podem não funcionar.

## Uso
Os testes unitários estão localizados no diretório `test` e podem ser executados usando o módulo `unittest` ou usando `pytest`. Isso não deve demorar muito, talvez alguns minutos, dependendo da sua máquina.

Para executar um ataque específico, você deve adicionar o código ao arquivo apropriado antes de executá-lo.

### Exemplo

Por exemplo, você quer atacar o RSA usando o ataque Boneh-Durfee, com os seguintes parâmetros (retirados de [test_rsa.py](https://github.com/jvdsn/crypto-attacks/blob/master/test/test_rsa.py)):```python
N = 88320836926176610260238895174120738360949322009576866758081671082752401596826820274141832913391890604999466444724537056453777218596634375604879123818123658076245218807184443147162102569631427096787406420042132112746340310992380094474893565028303466135529032341382899333117011402408049370805729286122880037249
e = 36224751658507610673165956970793195381480143363550601971796688201449789736497322700382657163240771111376677180786660893671085854060092736865293791299460933460067267613023891500397200389824179925263846148644777638774319680682025117466596019474987378275216579013846855328009375540444176771945272078755317168511

Adicione o seguinte código na parte inferior do arquivo boneh_durfee.py:```python 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, m=3) assert p * q == N print(f"Found {p = } and {q = }")

Então você pode simplesmente executar o arquivo usando Sage. Não importa de onde você o execute, o caminho do Python é definido automaticamente (você também pode chamar os ataques de outros arquivos Python, mas nesse caso terá que corrigir o caminho do Python você mesmo):```commandline
[crypto-attacks]$ sage -python attacks/rsa/boneh_durfee.py
INFO:root:Trying m = 3, t = 1...
DEBUG:root:Generating shifts...
DEBUG:root:Creating a lattice with 11 shifts (order = 'invlex', sort_shifts_reverse = False, sort_monomials_reverse = False)...
DEBUG:root:Reducing a 11 x 11 lattice...
DEBUG:root:Reconstructing polynomials (divide_original = True, modulus_bound = False, divide_gcd = True)...
DEBUG:root:Polynomial at row 8 is constant, ignoring...
DEBUG:root:Reconstructed polynomial has gcd 1312232632720549890113031660369306919929075823824696839212183146130434668203517349691252841557097914064120078389640402109017308806168467714230057403815071456395553717020189622129706447677967264344568789118172311850383406340547579993263937406518074980025897726255316031512238322022839331135299265704052474541497687419350763703993630899191179705015113329644753599872380152055902238937889027950089072598069861391599563222633064848996619752054685734260976071760984100109990150069201501748622288840900421607423175114026653242500476408861976142751384898489130281755466581359057847077651502734556259387442296763474369957121 with polynomial at 8, dividing...
DEBUG:root:Reconstructed 10 polynomials
DEBUG:root:Computing pairwise gcds to find trivial roots...
DEBUG:root:Using Groebner basis method to find roots...
DEBUG:root:Sequence length: 10, Groebner basis length: 1
DEBUG:root:Sequence length: 9, Groebner basis length: 1
DEBUG:root:Sequence length: 8, Groebner basis length: 1
DEBUG:root:Sequence length: 7, Groebner basis length: 2
DEBUG:root:Found Groebner basis with length 2, trying to find roots...
Found p = 7866790440964395011005623971351568677139336343167390105188826934257986271072664643571727955882500173182140478082778193338086048035817634545367411924942763 and q = 11227048386374621771175649743442169526805922745751610531569607663416378302561807690656370394330458335919244239976798600743588701676542461805061598571009923

Os parâmetros m e t, conforme mostrados no log de saída, merecem atenção especial. Esses parâmetros são usados em muitos algoritmos baseados em reticulados (raízes pequenas) para ajustar o tamanho do reticulado. Conceitualmente, m (às vezes chamado de k) e t representam o número de "deslocamentos" usados no reticulado, o que é aproximadamente igual ou proporcional ao número de linhas. Portanto, aumentar m e t aumentará o tamanho do reticulado, o que também aumenta o tempo necessário para realizar a redução do reticulado (atualmente usando LLL). Por outro lado, se m e t forem muito baixos, é possível que a redução do reticulado não resulte em vetores adequados, desperdiçando assim o tempo gasto na redução. Portanto, trata-se de um trade-off.

Na versão atual do projeto, m deve ser sempre fornecido pelo usuário (o valor padrão é 1). t pode, em alguns casos, ser calculado com base no método específico de raízes pequenas usado pelo ataque. No entanto, ainda pode ser ajustado pelo usuário. Em geral, há duas maneiras de usar esses tipos de parâmetros:

• Implementar um loop que começa em m = 1 até que uma resposta seja encontrada (exemplo abaixo). Essa é uma abordagem simples, mas corre o risco de desperdiçar tempo com cálculos inúteis com reticulados muito pequenos.``` m = 1 while True: res = attack(..., m=m) if res is not None: # The attack succeeded! break m += 1

* Implemente uma versão de depuração do ataque que você está tentando usar (com resultados conhecidos) e determine o valor de `m` que resulta em bons vetores de reticulado. Em seguida, chame diretamente o método de ataque com o valor correto de `m`.


## Ataques implementados
### Divisor Comum Aproximado
* [x] [Ataque polinomial multivariado](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/acd/mp.py) [^acd_mp]
* [x] [Ataque baseado em ortogonalidade](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/acd/ol.py) [^acd_ol]
* [x] [Ataque de aproximação diofantina simultânea](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/acd/sda.py) [^acd_sda]

### CBC
* [x] [Ataque de inversão de bits](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/cbc/bit_flipping.py)
* [x] [Ataque de recuperação de IV](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/cbc/iv_recovery.py)
* [x] [Ataque de oráculo de preenchimento](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/cbc/padding_oracle.py)

### CBC + CBC-MAC
* [x] [Ataque de reutilização de chave (encrypt-and-MAC)](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/cbc_and_cbc_mac/eam_key_reuse.py)
* [x] [Ataque de reutilização de chave (encrypt-then-MAC)](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/cbc_and_cbc_mac/etm_key_reuse.py)
* [x] [Ataque de reutilização de chave (MAC-then-encrypt)](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/cbc_and_cbc_mac/mte_key_reuse.py)

### CBC-MAC
* [x] [Ataque de extensão de comprimento](https://github.com/jvdsn/crypto-attacks/blob/master/attacks/cbc_mac/length_extension.py)