Introduction
This weekend we played NahamCon CTF 2020 and I decided to log this post-mortem solution that could help future challenges that involve random libs in python. It is post-mortem because we didn’t manage to solve, but after the end of the CTF I got some insights from the Official Discord Channel that helped my to finish the challenge.
Crypto - Elsa4
Elsa4
150 points
Back for another money grab, Elsa is singing “Frozen in Time” once more!
Yes, that information is intentionally not displayed properly.
Connect with: nc jh2i.com 50014
Description and Details
Since you connect in the server, it will display the following output:
_ ___
___| |___ ___| | |
| -_| |_ -| .'|_ |
|___|_|___|__,| |_| 07:49:00, 2020/06/14
If I was ever frozen in time
It wouldn't matter how when or why it would be
As long as I knew that you were next to me
Frozen in time for eternity
1. Encrypt
2. Decrypt
3. Info
>
We got 3 options where the first one is an oracle to cipher messages for us. We send a message, the server cipher the message and show to us the plaintext, Key, Encrypted and a Nonce.
> 1
plaintext = fireshell
Key = 9ndga5v6iq3kf42wocz_x8htjpsyr#meblu7
Nonce = �̷͠�̵̑�̸̏�̸̔ ̻̦�̴́�̴́
Encrypted = 982v9ktoj
In this case Nonce it’s only garbage. The second option is to decipher something that the server send to us.
> 2
Key = z2u_a48xwdsvn9jiop7mhfeyb6crq5#lk3gt
Nonce = �̷͠�̵̑�̸̏�̸̔ ̻̦�̴́�̴́
Encrypted = 8e__h2iaa2z29cqmovq95tpbnbzzcvj63to7
Decrypted = I don't know yet.
fail, bad decryption. incorrect plaintext.
The third one show to us some info (not some info, ESSENTIAL INFO).
> 3
alphabet = "#_23456789abcdefghijklmnopqrstuvwxyz"
nonce_chars = []
for _ in range(nonce_length):
nonce_chars.extend(random.sample(alphabet, 1))
This option show to us how the nonce is generated.
Solution
The first information about the challenge is to discover what cipher the server is using. After some time, one of the teammates discovered that they are probably using ElsieFour (a.k.a LC4 (similar pronunciation)). LC4 is a cipher decribed as a “low-tech cipher that can be computed by hand; but unlike many historical ciphers, LC4 is designed to be hard to break”. There is an article from 2017 that describes the details about this cipher (ElsieFour: A Low-Tech Authenticated Encryption Algorithm For Human-to-Human Communication). We reinforced our believes in that cipher, after find and read a github repo for LC4 that has similar examples with the challenge.
The second information and this is the one that we didn’t manage to discover during the CTF is that the description of the challenge was just as important as the title. We thought that the verse (part of the song The Best Wedding Songs Of All Time - Frozen In Time) was just shenanigans for the title. Since the challenge uses random.sample to create the nonce, the quotations about “frozen in time” were hinting that random was using time to seed the PRNG. After the CTF ends, I saw a comment in discord saying the following:
This comment just clicked why we didn’t manage to solve in time (at least that’s what I guessed). With the informations we had, we knew that it was necessary to discover the correct Nonce do decrypt the given message, but our most profitable strategy during the CTF was that the Nonce was fixed and we could brute force with a parallel code using the default length (6), but it wasn’t fixed between different connections.
So, after the CTF I code the “correct” solution. The algorithm works as the following:
- connect to the server
- encrypt a example message
- test a range of seeds to find the correct nonce for the example message
- decrypt the message from the server
- “profit”
I was using the default length for the nonce (6), setted the range of seed to test as range(currenttime, timethechallangewasreleased - 1 hour, -1) and after connecting in the server to check the answer it didn’t worked. At first I tough: “OK, maybe the length is 7 or 8.”; So I adjusted the code and connected again. This time my code found a valid nounce with lenght 7, but the server return that the decryption was wrong. So what! WHAT!?!
It wasn’t make any sense for me because the code was working properly locally (typical IT problem). After a while I started to read about how random.seed works and figure out that the problem is that seed is different based on the type of the variable (remembers that it was said ìnt(time.time())) that it will be different according to the version of the python. In CTFs I usually script in python 2 because of the differences that python 3 has to deal with strings and bytes (this video from LiveOverlow has examples what are these differences) and how could be annoying to deal with that. Here is a simple example of the seed differences:
[63620] crypto-elsa4|master > python2 -c 'import random; random.seed(1337); print(random.randint(0, 10000))'
6178
[63621] crypto-elsa4|master > python2 -c 'import random; random.seed(1337); print(random.randint(0, 10000))'
6178
[63621] crypto-elsa4|master > python3 -c 'import random; random.seed(1337); print(random.randint(0, 10000))'
8737
[63622] crypto-elsa4|master > python3 -c 'import random; random.seed(1337); print(random.randint(0, 10000))'
8737
So after catching these differences I ran the script in Python 3 and the flag just pop out in my face in less than 2 seconds. The Nonce was using the default length that is 6.
Solution Script
#!/usr/bin/python3
# -*- coding: UTF-8 -*-
import random, re, string, lc4
from pwn import *
host = 'jh2i.com'
port = 50014
ALPHABET = "#_23456789abcdefghijklmnopqrstuvwxyz"
def getnonce(seed, nonce_length):
random.seed(seed)
nonce_chars = []
for _ in range(nonce_length):
nonce_chars.extend(random.sample(ALPHABET, 1))
return ''.join(nonce_chars)
r = connect(host, port)
DEFAULTLENGTH = 6
plaintexttest = 'fireshell'
log.info('Using option 1 with the plaintext: %s', plaintexttest)
r.recvuntil('> ')
r.sendline('1')
r.recvuntil('plaintext = ')
r.sendline(plaintexttest)
msg = r.recvuntil('> ').decode('utf-8')
log.info('\n%s', msg)
key = re.findall(r'Key = (.+)\n', msg)[0]
log.info('Key: %s', key)
encrypted = re.findall(r'Encrypted = (.+)\n', msg)[0]
log.info('Encrypted: %s\n', encrypted)
log.info('Searching for the seed')
currenttime = int(time.time()) + 100
timezero = 1592128800 # Time that the challenge was released
log.info('TZ: %d', currenttime)
log.info('First seed: %d', currenttime)
log.info('Trying nonce lenght: %d', DEFAULTLENGTH)
with log.progress('Trying seed from %s to %s' % (str(currenttime), str(timezero))) as p:
for s in range(currenttime, timezero, -1):
gnonce = getnonce(s, DEFAULTLENGTH)
if s % 10 == 0:
p.status(str(s))
dec = lc4.decrypt(key, encrypted, nonce = gnonce)
if 'fireshell' in dec:
log.success('Found nouce at %d: %s\n\n', s, gnonce)
foundnonce = gnonce
break
log.info('Using option 2 to decrypt a text with the found nonce')
r.sendline('2')
msg = r.recvuntil('Decrypted = ').decode('utf-8')
key = re.findall(r'Key = (.+)\n', msg)[0]
log.info('Key: %s', key)
encrypted = re.findall(r'Encrypted = (.+)\n', msg)[0]
log.info('Encrypted: %s', key)
dec = lc4.decrypt(key, encrypted, nonce = foundnonce)
log.info('Dec: %s', dec)
r.sendline(dec)
msg = r.recvuntil('\n\n', drop = True).decode('utf-8')
log.success('Flag: %s', msg)
Execution output:
[+] Opening connection to jh2i.com on port 50014: Done
[*] Using option 1 with the plaintext: fireshell
[*]
Key = tomnce5uhb79i_wxdjlg4rzv2a#6fq3kpsy8
Nonce = �̷͠�̵̑�̸̏�̸̔ ̻̦�̴́�̴́
Encrypted = ipbyov4qo
1. Encrypt
2. Decrypt
3. Info
>
[*] Key: tomnce5uhb79i_wxdjlg4rzv2a#6fq3kpsy8
[*] Encrypted: ipbyov4qo
[*] Searching for the seed
[*] TZ: 1592131811
[*] First seed: 1592131811
[*] Trying nonce lenght: 6
[+] Trying seed from 1592131811 to 1592128800: Done
[+] Found nouce at 1592131711: 936l85
[*] Using option 2 to decrypt a text with the found nonce
[*] Key: 6#wqzauypnh4s5gkom8dbtivx9f3_7rce2jl
[*] Encrypted: 6#wqzauypnh4s5gkom8dbtivx9f3_7rce2jl
[*] Dec: izagxlsjn8c47f5hopkw6uy2dvtmr39qbe#_
[+] Flag: flag{elsa_uses_lc4_frozen_in_time}
And the flag is flag{elsa_uses_lc4_frozen_in_time}.