Tags: crypto stream-cipher
Rating:
## Jazzy
### Challenge
>Jazzy in the real world, but it's flashy and showy!
```
nc 76.74.178.201 31337
```
### Solution
Connecting to the server, we are given the following options:
```
------------------------------------------------------------------------
| ..:: Jazzy semantically secure cryptosystem ::.. |
| Try to break this cryptosystem and find the flag! |
------------------------------------------------------------------------
| Options: |
| [E]ncryption function |
| [F]lag (encrypted)! |
| [P]ublic key |
| [D]ecryption oracle |
| [Q]uit |
|----------------------------------------------------------------------|
```
Calling `E` we are given the source of the encryption
```python
def encrypt(msg, pubkey):
h = len(bin(len(bin(pubkey)[2:]))[2:]) - 1 # dirty log :/
m = bytes_to_long(msg)
if len(bin(m)[2:]) % h != 0:
m = '0' * (h - len(bin(m)[2:]) % h) + bin(m)[2:]
else:
m = bin(m)[2:]
t = len(m) // h
M = [m[h*i:h*i+h] for i in range(t)]
r = random.randint(1, pubkey)
s_0 = pow(r, 2, pubkey)
C = []
for i in range(t):
s_i = pow(s_0, 2, pubkey)
k = bin(s_i)[2:][-h:]
c = bin(int(M[i], 2) ^ int(k, 2))[2:].zfill(h)
C.append(c)
s_0 = s_i
enc = int(''.join(C), 2)
return (enc, pow(s_i, 2, pubkey))
```
I'll talk about this more later, but let's play with the server and see what it allows us to do first.
Sending the option `P` we get the `pubkey`
```
pubkey = 19386947523323881137657722758784550061106532690506305900249779841167576220076212135680639455022694670503210628255656646008011027142702455763327842867219209906085977668455830309111190774053501662218829125259002174637966634423791789251231110340244630214258655422173621444242489738175447333216354148711752466314530719614094724358835343148321688492410941279847726548532755612726470529315488889562870038948285553892644571111719902764495405902112917765163456381355663349414237105472911750206451801228088587783073435345892701332742065121188472147494459698861131293625595711112000070721340916959903684930522615446106875805793
```
Which for reasons below, I will now refer to as the modulus $n$. Sending the option `F`, we get the encryption of the flag, again with `pubkey` as a label, but from the encryption function, we know that this value is (or at least should be $s_{t+1} = s_t^2 \mod n$). Not sure why ASIS chose this confusing notation...
```
encrypt(flag, pubkey) = (513034390171324294434451277551689016606030017438707103869413492040051559571787250655384810990478248003042112532698503643742022419886333447600832984361864307529994477653561831340899157529404892382650382111633622198787716725365621822247147320745039924328861122790104611285962416151778910L, 1488429745298868766638479271207330114843847244232531062732057594917937561200978102167607190725732075771987314708915658110913826837267872416736589249787656499672811179741037216221767195188188763324278766203100220955272045310661887176873118511588238035347274102755393142846007358843931007832981307675991623888190387664964320071868166680149108371223039154927112978353227095505341351970335798938829053506618617396788719737045747877570660359923455754974907719535747353389095579477082285353626562184714935217407624849113205466008323762523449378494051510623802481835958533728111537252943447196357323856242125790983614239733L)
```
Lastly sending the option `D` we are given the prompt
```
| send an pair of integers, like (c, x), that you want to decrypt:
```
Being a wise guy, I tried sending the flag back to the server, but I was given the message
```
| this decryption is NOT allowed :P
```
Solving this challenge was easy after a bit of googling to try and see what this crypto system was. I noticed that the key stream was generated using a random number generator called [Blum Blum Shub](https://en.wikipedia.org/wiki/Blum_Blum_Shub). Looking for when this was used as a keystream, I stumbled upon the [Blum-Goldwasser Cryptosystem](https://en.wikipedia.org/wiki/Blum–Goldwasser_cryptosystem) and spending a little bit of time reading the Wikipedia page, I could tell that this was the right choice.
#### Adaptive chosen plaintext attack
Reading more closely, I spotted that the BG implementation is insecure against adaptive plaintext attacks when the attacker has access to a decryption oracle. This sounds great!!
The idea is that to decrypt some ciphertext $(\vec{c}, s)$, one can pick a generic ciphertext using the same seed $(\vec{a}, s)$ and then use the decryption oracle to find $m^\prime$. As the seed is the same, both $m^\prime$ and the flag $m$ have been encrypted with the same keystream and we can obtain the flag from $m = \vec{a} \oplus \vec{c} \oplus m^\prime$.
This sounds easy! Lets go back to the server and generate $m^\prime$:
```
| send an pair of integers, like (c, x), that you want to decrypt:
(513034390171324294434451277551689016606030017438707103869413492040051559571787250655384810990478248003042112532698503643742022419886333447600832984361864307529994477653561831340899157529404892382650382111633622198787716725365621822247147320745039924328861122790104611285962416151778910, 1488429745298868766638479271207330114843847244232531062732057594917937561200978102167607190725732075771987314708915658110913826837267872416736589249787656499672811179741037216221767195188188763324278766203100220955272045310661887176873118511588238035347274102755393142846007358843931007832981307675991623888190387664964320071868166680149108371223039154927112978353227095505341351970335798938829053506618617396788719737045747877570660359923455754974907719535747353389095579477082285353626562184714935217407624849113205466008323762523449378494051510623802481835958533728111537252943447196357323856242125790983614239733)
| this decryption is NOT allowed :P
```
Uh oh... it seems that the server checks the seed value and doesn't let us use this attack...
#### Just one more block
Okay, so if we can't use the same $s$ as the flag encryption, and we can't factor $n$ (waaaaaaay too big) what options do we have?
I dunno if this attack has a proper name, but I realised we could fool the server into decrypting the flag by adding a block to the end of the ciphertext. For every block that is encoded, the encryption protocol takes $s_i$ and calculates $s_{i+1} = s_i^2 \mod n$. As a result, if the ciphertext being decoded was exactly one block longer, then the seed value we would supply to the oracle wouldn't be $s$, but rather $s^2 \mod n$.
As we know `ct, s, n` we control enough data to solve the challenge, assuming that the server doesn't tell us off for sending $s^2 \mod n$...
So, this *should* bypass the seed check in the oracle and allow us to decrypt the flag. All we need to do is take the pair `(ct, s)` from the server, together with the modulus `n` , add `h` bits to the end of `ct` and square `s`. Sending this to the oracle will decrypt our ciphertext block by block, we can finally remove the last `h` bits (which will have decoded to garbage) and grab the flag.
To do this I wrote something quick and dirty
```python
n = 19386947523323881137657722758784550061106532690506305900249779841167576220076212135680639455022694670503210628255656646008011027142702455763327842867219209906085977668455830309111190774053501662218829125259002174637966634423791789251231110340244630214258655422173621444242489738175447333216354148711752466314530719614094724358835343148321688492410941279847726548532755612726470529315488889562870038948285553892644571111719902764495405902112917765163456381355663349414237105472911750206451801228088587783073435345892701332742065121188472147494459698861131293625595711112000070721340916959903684930522615446106875805793
h = len(bin(len(bin(n)[2:]))[2:]) - 1
flag_ct = 513034390171324294434451277551689016606030017438707103869413492040051559571787250655384810990478248003042112532698503643742022419886333447600832984361864307529994477653561831340899157529404892382650382111633622198787716725365621822247147320745039924328861122790104611285962416151778910
seed = 1488429745298868766638479271207330114843847244232531062732057594917937561200978102167607190725732075771987314708915658110913826837267872416736589249787656499672811179741037216221767195188188763324278766203100220955272045310661887176873118511588238035347274102755393142846007358843931007832981307675991623888190387664964320071868166680149108371223039154927112978353227095505341351970335798938829053506618617396788719737045747877570660359923455754974907719535747353389095579477082285353626562184714935217407624849113205466008323762523449378494051510623802481835958533728111537252943447196357323856242125790983614239733
seed_squared = pow(seed,2,n)
flag_extended = bin(flag_ct)[2:] + '1'*h
flag_extended = int(flag_extended, 2)
print(f"({flag_extended}, {seed_squared})")
```
Using the data collected above. Sending our slightly longer flag to the server gives us a decrypted message:
```
(1050694431070872155001756216425859106009149475714472148724558831698025594003020289342228092908499451910230246466966535462383661915927210900686505951973098101821428690234494630586161474620221219599667982564625658263117243853548793491962157712885841765025507579474134243913651028278843209727, 3216641374118298063210229377328115445643813442578456023987769065661762517695051834586452075939576983800791011462122765510295327568646398522659752628912802933208909111321539625480585977865621874640928715606628766855738533853630742505790835948213775188951805695531626048779789826277990208281243968206104294503971898862963118207505455918079294280929081526755227996190831742555093366364879064928874861060462753403017976763786404530509469825731935018035684983539175758425557263211403465858234005521025395515018046387350089113701767863479780051534190944394815574406100307489105693633714510667995574063150674428700480235811)
| the decrypted message is: 47771147116374265884489633343424974277884840496243413677482329815315049691915267634281287751924271959635398604756191897221446400520109091655450373658402419482516535670630080915290670126420548875478840451816545566711178369563850274167871301020132981380671014536902778264305709989256317962
```
Then we can simply grab the flag after chopping off 11 bits
```python
>>> from Crypto.Util.number import long_to_bytes
>>> flag_ext = 47771147116374265884489633343424974277884840496243413677482329815315049691915267634281287751924271959635398604756191897221446400520109091655450373658402419482516535670630080915290670126420548875478840451816545566711178369563850274167871301020132981380671014536902778264305709989256317962
>>> flag_bin = bin(flag_ext)[2:-11]
>>> flag_int = int(flag_bin, 2)
>>> flag = long_to_bytes(flag_int)
>>> print(flag)
b'((((......:::::: Great! the flag is: ASIS{BlUM_G0ldwaS53R_cryptOsySt3M_Iz_HI9hlY_vUlNEr4bl3_70_CCA!?} ::::::......))))'
```
No pwntools cracked out to do this one in a stylish way, but we still grab the flag!
#### Flag
`ASIS{BlUM_G0ldwaS53R_cryptOsySt3M_Iz_HI9hlY_vUlNEr4bl3_70_CCA!?}`
