Tags: affine crypto bruteforce
Rating:
The attachment contains the following files:
```console
unzip -l mfine.zip
Archive: mfine.zip
Length Date Time Name
--------- ---------- ----- ----
539 11-17-2021 13:17 chal.py
630 11-17-2021 13:16 cipher.txt
--------- -------
1169 2 files
```
The `chal.py` file contains the following simple encryption code:
```python
import random
def encrypt(plaintext):
ciphertext = ''
for letter in plaintext:
i = ALPHA.index(letter)
c = (a*i + b) % m
ciphertext += ALPHA[c]
return ciphertext
ALPHA = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ{}_ #"
m = len(ALPHA)
a = random.randrange(1, m)
b = random.randrange(1, m)
message = open("message.txt").read().replace('\n', '')
cipher = encrypt(message)
with open("cipher.txt", 'w') as f:
for i in range(0,len(cipher),64):
f.write( cipher[i:i+64]+'\n' )
```
It basically implements the [Affine Cipher](https://en.wikipedia.org/wiki/Affine_cipher). The
character set length is 41.
```python
In [163]: len("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ{}_ #")
Out[163]: 41
```
This means the total number of possible keys is 1681 and is feasibly bruteforceable.
```python
In [164]: pow(41, 2)
Out[164]: 1681
```
The `cipher.txt` file contains the encrypted message that we have to decrypt:
```
RVWA6IIHTWAJH1VWEAH0A6AR 1WAFIA2FTF6G1V6XWRHJA0DX0RHRDRHFTAJH1VW
EAQVWEWAW6JVAGWRRWEAHTA6TA6G1V6XWRAH0A2611W5ARFAHR0ATD2WEHJAWSDH
#6GWTRAWTJE 1RW5AD0HT4A6A0H21GWA26RVW26RHJ6GAIDTJRHFTA6T5AJFT#WE
RW5AX6JUARFA6AGWRRWEARVWAIG64AIFEA FDAH0A#DGTJFTBM#ME RV9T4OJ8TO
XMOXENUMTO9IO NDO6EMOZ28EROMTND4V_ARVWAIFE2DG6AD0W5A2W6T0ARV6RAW
6JVAGWRRWEAWTJE 1R0ARFAFTWAFRVWEAGWRRWEA6T5AX6JUA646HTA2W6THT4AR
VWAJH1VWEAH0AW00WTRH6GG A6A0R6T56E5A0DX0RHRDRHFTAJH1VWEAQHRVA6AE
DGWA4F#WETHT4AQVHJVAGWRRWEA4FW0ARFAQVHJVA0HTJWARVWA6IIHTWAJH1VWE
AH0A0RHGGA6A2FTF6G1V6XWRHJA0DX0RHRDRHFTAJH1VWEAHRAHTVWEHR0ARVWAQ
W6UTW00W0AFIARV6RAJG600AFIAJH1VWE0
```
The solver script to this is given as follows:
```python
#!/usr/bin/env python
# Requires python 3.8+
import itertools
ALPHA = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ{}_ #"
m = len(ALPHA)
def encrypt(plaintext, a, b):
ciphertext = ''
for letter in plaintext:
i = ALPHA.index(letter)
c = (a*i + b) % m
ciphertext += ALPHA[c]
return ciphertext
def decrypt(ciphertext, a, b):
plaintext = ''
inv = pow(a, -1, m)
for letter in ciphertext:
i = ALPHA.index(letter)
p = ((i - b) * inv) % m
plaintext += ALPHA[p]
return plaintext
def main():
ciphertext = open("cipher.txt").read().replace('\n', '')
print('Ciphertext: {}'.format(ciphertext))
possible_decrypts = []
for a, b in itertools.product(range(1, m), range(1, m)):
plaintext = decrypt(ciphertext, a, b)
print('Key ({}, {}): {}'.format(a, b, plaintext))
if 'flag' in plaintext.lower():
possible_decrypts.append((a, b, plaintext))
print("\nPossible Decryptions:\n")
for a, b, plaintext in possible_decrypts:
print('Key ({}, {}): {}'.format(a, b, plaintext))
if __name__ == '__main__':
main()
```
Running the script gives us the following output:
```console
$ python exploit.py
Ciphertext: RVWA6IIHTWAJH1VWEAH0A6AR 1WAFIA2FTF6G1V6XWRHJA0DX0RHRDRHFTAJH1VWEAQVWEWAW6JVAGWRRWEAHTA6TA6G1V6XWRAH0A2611W5ARFAHR0ATD2WEHJAWSDH#6GWTRAWTJE 1RW5AD0HT4A6A0H21GWA26RVW26RHJ6GAIDTJRHFTA6T5AJFT#WERW5AX6JUARFA6AGWRRWEARVWAIG64AIFEA FDAH0A#DGTJFTBM#ME RV9T4OJ8TOXMOXENUMTO9IO NDO6EMOZ28EROMTND4V_ARVWAIFE2DG6AD0W5A2W6T0ARV6RAW6JVAGWRRWEAWTJE 1R0ARFAFTWAFRVWEAGWRRWEA6T5AX6JUA646HTA2W6THT4ARVWAJH1VWEAH0AW00WTRH6GG A6A0R6T56E5A0DX0RHRDRHFTAJH1VWEAQHRVA6AEDGWA4F#WETHT4AQVHJVAGWRRWEA4FW0ARFAQVHJVA0HTJWARVWA6IIHTWAJH1VWEAH0A0RHGGA6A2FTF6G1V6XWRHJA0DX0RHRDRHFTAJH1VWEAHRAHTVWEHR0ARVWAQW6UTW00W0AFIARV6RAJG600AFIAJH1VWE0
Key (1, 1): QUV95HHGSV9IG0UVD9G#959Q_0V9EH91ESE5F0U5WVQGI9#CW#QGQCQGES9IG0UVD9PUVDV9V5IU9FVQQVD9GS95S95F0U5WVQ9G#91500V49QE9GQ#9SC1VDGI9VRCG 5FVSQ9VSID_0QV49C#GS3959#G10FV915QUV15QGI5F9HCSIQGES95S49IES VDQV49W5IT9QE959FVQQVD9QUV9HF539HED9_EC9G#9 CFSIESAL LD_QU8S3NI7SNWLNWDMTLSN8HN_MCN5DLNY17DQNLSMC3U}9QUV9HED1CF59C#V491V5S#9QU5Q9V5IU9FVQQVD9VSID_0Q#9QE9ESV9EQUVD9FVQQVD95S49W5IT9535GS91V5SGS39QUV9IG0UVD9G#9V##VSQG5FF_959#Q5S45D49#CW#QGQCQGES9IG0UVD9PGQU959DCFV93E VDSGS39PUGIU9FVQQVD93EV#9QE9PUGIU9#GSIV9QUV95HHGSV9IG0UVD9G#9#QGFF9591ESE5F0U5WVQGI9#CW#QGQCQGES9IG0UVD9GQ9GSUVDGQ#9QUV9PV5TSV##V#9EH9QU5Q9IF5##9EH9IG0UVD#
Key (1, 2): PTU84GGFRU8HF#TUC8F 848P}#U8DG80DRD4E#T4VUPFH8 BV PFPBPFDR8HF#TUC8OTUCU8U4HT8EUPPUC8FR84R84E#T4VUP8F 804##U38PD8FP 8RB0UCFH8UQBF_4EURP8URHC}#PU38B FR2848 F0#EU804PTU04PFH4E8GBRHPFDR84R38HDR_UCPU38V4HS8PD848EUPPUC8PTU8GE428GDC8}DB8F 8_BERHDR9K_KC}PT7R2MH6RMVKMVCLSKRM7GM}LBM4CKMX06CPMKRLB2T{8PTU8GDC0BE48B U380U4R 8PT4P8U4HT8EUPPUC8URHC}#P 8PD8DRU8DPTUC8EUPPUC84R38V4HS8424FR80U4RFR28PTU8HF#TUC8F 8U URPF4EE}848 P4R34C38 BV PFPBPFDR8HF#TUC8OFPT848CBEU82D_UCRFR28OTFHT8EUPPUC82DU 8PD8OTFHT8 FRHU8PTU84GGFRU8HF#TUC8F 8 PFEE8480DRD4E#T4VUPFH8 BV PFPBPFDR8HF#TUC8FP8FRTUCFP 8PTU8OU4SRU U 8DG8PT4P8HE4 8DG8HF#TUC
Key (1, 3): OST73FFEQT7GE STB7E_737O{ T7CF7#CQC3D S3UTOEG7_AU_OEOAOECQ7GE STB7NSTBT7T3GS7DTOOTB7EQ73Q73D S3UTO7E_7#3 T27OC7EO_7QA#TBEG7TPAE}3DTQO7TQGB{ OT27A_EQ1737_E# DT7#3OST#3OEG3D7FAQGOECQ73Q27GCQ}TBOT27U3GR7OC737DTOOTB7OST7FD317FCB7{CA7E_7}ADQGCQ8J}JB{OS6Q1LG5QLUJLUBKRJQL6FL{KAL3BJLW#5BOLJQKA1SZ7OST7FCB#AD37A_T27#T3Q_7OS3O7T3GS7DTOOTB7TQGB{ O_7OC7CQT7COSTB7DTOOTB73Q27U3GR7313EQ7#T3QEQ17OST7GE STB7E_7T__TQOE3DD{737_O3Q23B27_AU_OEOAOECQ7GE STB7NEOS737BADT71C}TBQEQ17NSEGS7DTOOTB71CT_7OC7NSEGS7_EQGT7OST73FFEQT7GE STB7E_7_OEDD737#CQC3D S3UTOEG7_AU_OEOAOECQ7GE STB7EO7EQSTBEO_7OST7NT3RQT__T_7CF7OS3O7GD3__7CF7GE STB_
Key (1, 4): NRS62EEDPS6FD_RSA6D}626NZ_S6BE6 BPB2C_R2TSNDF6}9T}NDN9NDBP6FD_RSA6MRSAS6S2FR6CSNNSA6DP62P62C_R2TSN6D}6 2__S16NB6DN}6P9 SADF6SO9D{2CSPN6SPFAZ_NS169}DP0626}D _CS6 2NRS 2NDF2C6E9PFNDBP62P16FBP{SANS16T2FQ6NB626CSNNSA6NRS6EC206EBA6ZB96D}6{9CPFBP7I{IAZNR5P0KF4PKTIKTAJQIPK5EKZJ9K2AIKV 4ANKIPJ90RY6NRS6EBA 9C269}S16 S2P}6NR2N6S2FR6CSNNSA6SPFAZ_N}6NB6BPS6BNRSA6CSNNSA62P16T2FQ6202DP6 S2PDP06NRS6FD_RSA6D}6S}}SPND2CCZ626}N2P12A16}9T}NDN9NDBP6FD_RSA6MDNR626A9CS60B{SAPDP06MRDFR6CSNNSA60BS}6NB6MRDFR6}DPFS6NRS62EEDPS6FD_RSA6D}6}NDCC626 BPB2C_R2TSNDF6}9T}NDN9NDBP6FD_RSA6DN6DPRSADN}6NRS6MS2QPS}}S}6BE6NR2N6FC2}}6BE6FD_RSA}
...
Possible Decryptions:
Key (27, 23): THE AFFINE CIPHER IS A TYPE OF MONOALPHABETIC SUBSTITUTION CIPHER WHERE EACH LETTER IN AN ALPHABET IS MAPPED TO ITS NUMERIC EQUIVALENT ENCRYPTED USING A SIMPLE MATHEMATICAL FUNCTION AND CONVERTED BACK TO A LETTER THE FLAG FOR YOU IS VULNCON{3V3RYTH1NG_C4N_B3_BR0K3N_1F_Y0U_AR3_5M4RT_3N0UGH} THE FORMULA USED MEANS THAT EACH LETTER ENCRYPTS TO ONE OTHER LETTER AND BACK AGAIN MEANING THE CIPHER IS ESSENTIALLY A STANDARD SUBSTITUTION CIPHER WITH A RULE GOVERNING WHICH LETTER GOES TO WHICH SINCE THE AFFINE CIPHER IS STILL A MONOALPHABETIC SUBSTITUTION CIPHER IT INHERITS THE WEAKNESSES OF THAT CLASS OF CIPHERS
```
**Flag:** `VULNCON{g00d_luck_4nd_Have_fun}`
