---
# System prepended metadata

title: ImaginaryCTF 2022 - Cryptography

---

# ImaginaryCTF 2022 - Cryptography

## emojis

Description
> To be or not to be, that is the question. Sadly the challenge doesn't look nearly as good unless you have a fancy terminal 😦

Attachments
> emojis.txt

**$ cat emojis.txt**
👎👍👍👎👍👎👎👍👎👍👍👎👎👎👍👍👎👍👍👍👎👍👎👎👎👍👍👎👎👍👍👎👎👍👍👍👍👎👍👍👎👍👍👎👎👍👎👍👎👍👍👎👍👍👍👎👎👍👍👎👎👎👍👍👎👎👍👍👎👎👎👎👎👍👍👎👎👍👎👎👎👍👍👎👍👎👎👍👎👍👍👎👍👍👍👎👎👍👍👎👎👍👍👍👎👍👎👍👍👍👍👍👎👍👍👎👍👎👎👍👎👍👍👍👎👎👍👍👎👍👎👍👍👍👍👍👎👍👍👎👍👍👍👎👎👎👍👍👎👎👎👎👎👍👍👍👎👍👎👎👎👍👎👍👍👍👍👍👎👍👍👎👎👍👎👍👎👍👍👎👍👍👍👎👎👍👍👎👎👎👍👍👎👍👍👍👎👎👍👎👎👍👍👍👍👎👎👍👎👍👍👍👎👎👎👎👎👍👍👍👎👍👎👎👎👍👍👎👍👎👎👍👎👎👍👍👎👎👎👎👎👍👍👎👍👍👍👎👎👍👎👍👍👍👍👍👎👎👍👍👎👎👎👍👎👍👍👎👎👎👍👎👎👎👍👍👎👎👍👎👎👍👍👎👎👍👎👍👎👎👍👍👎👎👎👎👎👍👍👎👎👍👎👎👎👎👍👍👎👍👎👎👎👎👍👍👎👎👍👍👎👍👍👍👍👍👎👍

Convert to binary: 0110100101100011011101000110011001111011011001010110111001100011001100000110010001101001011011100110011101011111011010010111001101011111011011100011000001110100010111110110010101101110011000110111001001111001011100000111010001101001001100000110111001011111001100010110001000110010011001010011000001100100001101000011001101111101

**Flag: ictf{enc0ding_is_n0t_encrypti0n_1b2e0d43}**

## smoll
Description
>Just a regular, run-of-the-mill RSA challenge, right? Right?
>[smoll.py](https://cdn.discordapp.com/attachments/732682111462539276/997400337948348416/smoll.py#smoll.py)
>[output.txt](https://cdn.discordapp.com/attachments/732682111462539276/997400357707718726/output.txt#output.txt)

Send `n` to [factorDB](factordb.com) and we get the `p, q`

`solve.py`
```python
from Crypto.Util.number import *
from factordb.factordb import FactorDB
n = 13499674168194561466922316170242276798504319181439855249990301432638272860625833163910240845751072537454409673251895471438416265237739552031051231793428184850123919306354002012853393046964765903473183152496753902632017353507140401241943223024609065186313736615344552390240803401818454235028841174032276853980750514304794215328089
e = 65537
ct = 12788784649128212003443801911238808677531529190358823987334139319133754409389076097878414688640165839022887582926546173865855012998136944892452542475239921395969959310532820340139252675765294080402729272319702232876148895288145134547288146650876233255475567026292174825779608187676620580631055656699361300542021447857973327523254
f = FactorDB(n)
f.connect()
[p, q] = (f.get_factor_list())
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(ct, d, n)
print(long_to_bytes(m))

```
**Flag: ictf{wh4t_1f_w3_sh4r3d_0ur_l4rge$t_fact0r_jk_unl3ss??}**
## Secure Encoding: Hex
Description
>Cryptograms == encryption, right? Flag is readable English.
>[encode.py](https://cdn.discordapp.com/attachments/732682111462539276/997392720698028103/encode.py#encode.py)
>[out.txt](https://cdn.discordapp.com/attachments/732682111462539276/997392745457012846/out.txt#out.txt)

The flag is encrypted by changing the bytes of `flag.hex()`
We know the format flag is ictf {} so we can recover d
`b"ictf{}".hex()="696374667b7d"`
```
0d0b18001e060d090d1802131dcf011302080ccf0c070b0f080d0701cf00181116
696374667b......................................................7d
```
So d will have elements:
```
d= {'0': '6',
    'd': '9',
    'b': '3',
    '8': '4',
    '1': '7',
    'e': 'b',
    '6': 'd'}
```
And `ciphertext = 696374667b6d69696974627379cf677362646ccf6c67636f64696767cf6674777d`
When we decode the ciphertext:`ictf{miiitbsy\xcfgsbdl\xcflgcodigg\xcfftw}`
We can guess that the first word of the flag is `military` 
```
d = {
    '0': '6',
    'd': '9',
    'b': '3',
    '1': '7',
    '8': '4',
    'e': 'b',
    '9': 'c',
    '2': '1',
    '3': '2',
    '6': 'd'
}
```
`ciphertext = 696374667b6d696c6974617279cf677261646ccf6c67636f64696767cf6674777d`
`decode ciphertext: ictf{military\xcfgradl\xcflgcodigg\xcfftw}`
Guessing `gradl` is `grade`
```
d = {
    '0': '6',
    'd': '9',
    'b': '3',
    '1': '7',
    '8': '4',
    'e': 'b',
    '9': 'c',
    '2': '1',
    '3': '2',
    'c': '5',
    '6': 'd'
}
```
`ciphertext = 696374667b6d696c69746172795f67726164655f6567636f646967675f6674777d`
`decode ciphertext: ictf{military_grade_egcodigg_ftw}`
Guessing `egcodigg` is `encoding` we get flag
`solve.py`
```python
c = "0d0b18001e060d090d1802131dcf011302080ccf0c070b0f080d0701cf00181116"
d = {
    '0': '6',
    'd': '9',
    'b': '3',
    '1': '7',
    '8': '4',
    'e': 'b',
    '9': 'c',
    '2': '1',
    '3': '2',
    '7': 'e',
    'c': '5',
    '6': 'd'
}
p = ""
for i in c:
    try:
        a = d[i]
        p += a
    except:
        p += i
print(bytes.fromhex(p))

```
**Flag: ictf{military_grade_encoding_ftw}**

## huge
Description
>Huge primes = huge security
>[chal.py](https://cdn.discordapp.com/attachments/732682111462539276/997391504760905768/chal.py#chal.py)
>[output.txt](https://cdn.discordapp.com/attachments/732682111462539276/997391527401771068/out.txt#output.txt)

We send n to [Integer factorization calculator](https://www.alpertron.com.ar/ECM.HTM) and get `phi`
![](https://i.imgur.com/uvTihED.png)
`solve.py`
```python
from Crypto.Util.number import *
n = 257827703087398016057355158654193468564980243813004452658087616586210487667215030370871398983230710387803731676134007721137156696714627083072326445637415561591372586919746606752675050732692230618293581354674196658443898625965651230501721590806987488038754683843111434873697465691139129703835890867256688046172118591
e = 65537
c = 194667317703687479298989188290833629421904543231503224641743768867721632949682167895699280370759100055314992068135383846690184090232092994595979623784341194946153538127175310278245722299688212621004144260665233469561373125699948009903943019071999887294005117156960295183926108287198987970959145603429337056005819069
phi=int("238 940154 401626 938037 848370 480225 183045 581769 211725 031481 021020 007970 362783 588965 693807 273855 047475 931562 553093 129263 532876 569906 106451 113480 591159 727935 347588 408235 764799 039034 556484 596551 260176 507450 085252 133677 350349 066373 844187 940165 049949 179091 946213 517645 837708 200090 091217 192271 487206 162432 000000 000000 000000".replace(" ",''))
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

```
**Flag: ictf{sm4ll_pr1mes_are_n0_n0_9b129443}**

## cbc
Description
>I don't trust everyone's CBC implementations. So I rolled my own, with A HUNDRED PERCENT GUARANTEE OF DATA INTEGRITY!
>[cbc.py](https://cdn.discordapp.com/attachments/732682111462539276/997393898919960586/cbc.py#cbc.py)

block[i] is encrypted using AES ECB mode using the key is block[i-1] so we can recover the flag
`solve.py`
```python
from Crypto.Cipher import AES
ct = b"\xa2\xb8 <\xf2\x85\xa3-\xd1\x1aM}\xa9\xfd4\xfag<p\x0e\xb7|\xeb\x05\xcbc\xc3\x1e\xc3\xefT\x80\xd3\xa4 ~$\xceXb\x9a\x04\xf0\xc6\xb6\xd6\x1c\x95\xd1(O\xcfx\xf2z_\xc3\x87\xa6\xe9\x00\x1d\x9f\xa7\x0bm\xca\xea\x1e\x95T[Q\x80\x07we\x96)t\xdd\xa9A 7dZ\x9d\xfc\xdbA\x14\xda9\xf3\xeag\xe3\x1a\xc8\xad\x1cnL\x91\xf6\x83'\xaa\xaf\xf3i\xc0t=\xcd\x02K\x81\xb6\xfa.@\xde\xf5\xaf\xa3\xf1\xe3\xb4?\xf9,\xb2:i\x13x\xea1\xa0\xc1\xb9\x84"
blocks = [ct[i:i+16] for i in range(0, len(ct), 16)]
p = []
for i in range(1, len(blocks)):
    key = blocks[i-1]
    cipher = AES.new(key, AES.MODE_ECB)
    pt = cipher.decrypt(blocks[i])
    p.append(pt)
print(b''.join(p))

```
**Flag: ictf{i_guess_i_implemented_cbc_wrong_02b413a9}**

## otp
Description
>Encrypt your messages with our new OTP service. Your messages will never again be readable to anyone.
>[otp.py](https://cdn.discordapp.com/attachments/732682111462539276/997397659860086794/otp.py#otp.py)
>`nc otp.chal.imaginaryctf.org 1337`

Apply statistical probability to recount the number of occurrences of the flag bit in 100 attempts to get the encrypted flag
If the number of occurrences is greater than 50, it is bit 1, less than 50 is bit 0

`solve.py`
```python
from Crypto.Util.number import *
from pwn import *
io = connect("otp.chal.imaginaryctf.org", 1337)
list = [0]*(49*8)
for i in range(100):
    io.sendlineafter(b'Enter plaintext:', b'FLAG')
    io.recvuntil(b'Encrypted flag:')
    enc_flag = io.recvuntil(b'\n').strip()
    binary = bin(int(enc_flag, 16))[2:].rjust(392, '0')
    for j in range(len(binary)):
        if binary[j] == '1':
            list[j] += 1

bina = ""
for i in list:
    if i >= 50:
        bina += '0'
    else:
        bina += '1'
print(long_to_bytes(int(bina, 2)))
```
**Flag: ictf{benfords_law_catching_tax_fraud_since_1938}**
## hash

Description
> My passwords are safe and secure with the use of sha42!
> nc hash.chal.imaginaryctf.org 1337

Attachments
> hash.py
> jbox.txt

jbox.txt
```
100011010000011001011101010011101111110001
100001100010111001110100101000001110100100
110100100110011001000100101010110101001100
101100100010100010100101010111010011100111
010100100111111100011101100111110110101101
010101001000000010110101001100010010111001
111110011100000001011101000110101110111111
000000101111001111010011101110010110111100
111101100110100001100001100111000001111011
111111000001111001101100101101010110101110
000100011011110101101111000100111010011111
100100110110001001011100011110011101011110
100110011010001011011011001001001001001101
101100110001111010100010111000011000001100
000111110001100000001010101001011101001100
011100010011100010010111000010000101000011
100101111000100010100100100001111110111010
011000010001000101000100111110000100011111
111111001010011010011001001111000000111011
111001010110001000000001101011100011111001
101010011111000111000110101011110111101110
001110111101000101000011010111011110100111
100101011101001001110110111011010001111001
000101011111111000110001110011110101101100
110111110010010000110010010110111001011111
000010001001100010000101101110111011000100
101110000100110011111100110101111110110000
011001001100010100100011110010110101011000
001001000010010000100101111011101110001101
111001100110100110100011101010101000110000
```

hash.py
```python
#!/usr/bin/env python3

import string
import random

config = [[int(a) for a in n.strip()] for n in open("jbox.txt").readlines()] # sbox pbox jack in the box

# secure hashing algorithm 42
def sha42(s: bytes, rounds=42):
  out = [0]*21
  for round in range(rounds):
    for c in range(len(s)):
      if config[((c//21)+round)%len(config)][c%21] == 1:
        out[(c+round)%21] ^= s[c]
  return bytes(out).hex()

def main():
  print("Can you guess my passwords?")
  for trial in range(50):
    print(f"--------ROUND {trial}--------")
    password = "".join([random.choice(string.printable) for _ in range(random.randint(15,20))]).encode()
    hash = sha42(password)
    print(f"sha42(password) = {hash}")
    guess = bytes.fromhex(input("hex(password) = ").strip())
    if sha42(guess) == hash:
      print("Correct!")
    else:
      print("Incorrect. Try again next time.")
      exit(-1)
  flag = open("flag.txt", "r").read()
  print(f"Congrats! Your flag is: {flag}")

if __name__ == "__main__":
  main()
```

The `sha42` function takes two input, `s` for bytes being digested and `rounds` (default is 42), and returns 21-byte hash value. Each round the `sha42` randomly XORs the `out[(c+round)%21]` with `s[c]` based on `jbox`, `round` and `c` parameters. All three `jbox`, `round` are known value and `c` parameter just depends on `len(s)`.

The challenge requires us to send an input (in hex) that has the same hash digest as the hidden password. We can find this by solving linear equations over GF(2).

We have `M * s = out`. `M` is GF(2) 168x168 matrix, `out` is known hash value, and `s` is the input we need to find.

First build a matrix that has `determinant` not equal to 0 (Matrix requirement to have an `inverse`). Note that M is just based on `jbox`, `round` and `c` parameters, so we can build M for a given `len(s)`.

```python
from sage.all import *
from Crypto.Util.number import long_to_bytes
from pwn import remote

config = [[int(a) for a in n.strip()] for n in open("jbox.txt").readlines()] # sbox pbox jack in the box

# secure hashing algorithm 42
def sha42(s: bytes, rounds=42):
  out = [0]*21
  for round in range(rounds):
    for c in range(len(s)):
      if config[((c//21)+round)%len(config)][c%21] == 1:
        out[(c+round)%21] ^= s[c]
  return bytes(out).hex()

def build_matrix(rounds=42):
  M = [list(bytes(168)) for _ in range(168)]
  for round in range(rounds):
    for c in range(21*6):
      if config[((c//21)+round)%len(config)][c%21] == 1:
        for i in range(8):
          M[((c+round)%21)*8+i][8*(c%21)+i] ^= 1
  return M

# print(sha42(b'abcdefghijklmnop'))
# print(sha42(bytes.fromhex('0f647b0861127f63131c660b0c18706e771f600d610f647b0861127f63131c660b0c18706e771f600d610f647b0861127f63131c660b0c18706e771f600d610f647b0861127f63131c660b0c18706e771f600d610f647b0861127f63131c660b0c18706e771f600d610f647b0861127f63131c660b0c18706e771f600d61')))

M = matrix(GF(2),build_matrix())
print(det(M))
r = remote("hash.chal.imaginaryctf.org", 1337)
for i in range(50):
  r.recvuntil(b"sha42(password) = ")
  hash = r.recvline().strip()
  h = bin(int(hash,16))[2:].zfill(168)
  h = vector(GF(2),list(h))
  m = M.solve_right(h)
  m = int(''.join(map(str,m)),2)
  m = long_to_bytes(m).hex()*6
  r.sendlineafter(b"hex(password) = ",m.encode())
  print(r.recvline())
print(r.recvline())
```

**Flag: ictf{pls_d0nt_r0ll_y0ur_0wn_hashes_109b14d1}**

## stream

Description
> HELP! I encrypted my files with this program I downloaded from the internet. Can you recover my 42-byte flag?

Attachments
> stream
> out.txt

Simply reverse the `stream`, the cipher encrypts 8 bytes at a time and then update the key by squaring it (v3 *= v3).

![](https://i.imgur.com/TJH3RsS.png)

Note that we know the flag begins with `ictf{` so we have to brute force the next three bytes ~256**3 possibilities.

```python
import threading
from Crypto.Util.number import *
import string
import time
t = int(time.time())

chars = string.ascii_letters +string.digits + string.punctuation

def xor(a,b):
    return bytes([x^y for x,y in zip(a,b)])

ct = open("out.txt","rb").read()
key = xor(ct[:5],b"ictf{")
c = [ct[i:i+8] for i in range(0,len(ct),8)]
def brute_force(start,stop,key):
    for i in range(start,stop):
        k = key + i.to_bytes(3,"big")
        flag = b""
        for j in c[:5]:
            flag += xor(k,j)
            k = bytes_to_long(k[::-1])
            k *= k
            k = long_to_bytes(k)[::-1]
        try:
            flag = flag.decode()
            if all([ff in chars for ff in flag]):
                print(flag,i,int(time.time()-t))
        except:
            continue

for i in range(0,256**3,256**2):
    threading.Thread(target=brute_force,args=(i,i+256**2,key)).start()
```

**Flag: ictf{y0u_rec0vered_my_keystream_901bf2e4}**

## Lorge
Description
>I guess smoll needed a revenge after all 😭

Attachments
>`Lorge.py`
>`output.txt`

`Lorge.py`
```python
from secret import p, q
from sage.all import factor

for r in [p, q]:
    for s, _ in factor(r - 1):
        assert int(s).bit_length() <= 25

n = p * q
e = 0x10001

with open("flag.txt", "rb") as f:
    flag = int.from_bytes(f.read().strip(), "big")
assert flag < n

ct = pow(flag, e, n)
print(f"{n = }")
print(f"{e = }")
print(f"{ct = }")

```

`output.txt`
```
n = 63038895359658613740840475285214364620931775593017844102959979092033246293689886425959090682918827974981982265129797739561818809641574878138225207990868931316825055004052189441093747106855659893695637218915533940578672431813317992655224496134300271524374912502175195904393797412770270676558054466831561609036199966477
e = 65537
ct = 60515029337308681079476677877525631415600527185785323978384495461916047877351538207473264679842349366162035496831534576192102896080638477601954951097077261305183669746007206897469286005836283690807247174941785091487066018014838515240575628587875110061769222088950451112650700101446260617299040589650363814995825303369
```

`n` cannot be factored but we know `p-1` and `q-1` can be factored to small primes
We can calculate multiples of phi by calculating the product of primes less than 2**25
![](https://i.imgur.com/ycyMIe2.png)
`solve.sage`
```python=
from Crypto.Util.number import *
from sage.all import *
n = 63038895359658613740840475285214364620931775593017844102959979092033246293689886425959090682918827974981982265129797739561818809641574878138225207990868931316825055004052189441093747106855659893695637218915533940578672431813317992655224496134300271524374912502175195904393797412770270676558054466831561609036199966477
e = 65537
ct = 60515029337308681079476677877525631415600527185785323978384495461916047877351538207473264679842349366162035496831534576192102896080638477601954951097077261305183669746007206897469286005836283690807247174941785091487066018014838515240575628587875110061769222088950451112650700101446260617299040589650363814995825303369
list = []
a = 2
while a < 2**25:
    list.append(a)
    a = next_prime(a)

phi = mul(list)
phi = phi//e
d = inverse_mod(e, phi)
m = pow(ct, d, n)
# 1413028697349316750579237809920780290701967455820763866800100340354559200775427795287613405511628907717269981856466740772708143832854562658994863278869717373
print(long_to_bytes(int(m)))
# b'ictf{why_d1d_sm0ll_3v3n_sh0w_up_on_f4ct0rdb???_That_m4d3_m3_sad!}'

```
**Flag: ictf{why_d1d_sm0ll_3v3n_sh0w_up_on_f4ct0rdb???_That_m4d3_m3_sad!}**