Pragyan 2018 - RSA (200 Points)
Masalah
Rivest, Shamir and Aldeman’s quest (200pts)
4 hours, 53 minutes, 57 seconds remaining
Rivest comes up with an encryption, and Shamir creates a service for decrypting any cipher text encrypted using Rivests’s encryption. Aldeman is asked to decrypt a specific ciphertext, but he is not able to do so directly through Shamir’s service. Help him out.
The service is running at 128.199.224.175:34000
The encrypted text is :-
a0b75ef5dfd9ab0de9aa8c36a9c5aa28a924128a62826740ac3986efac69e2b85fc0df803e80da04c5f803726689e5f3134178de3cb203f6aebca22b376f7205d93a7224aca82cbbdc382200a1749fee095dfebe2aaabf99b622e4343bf5423cf6527433e26273e67d576157bf65a9258f613be9ad88d7b50350a89e676ae462
Parameters :-
N : 00:b9:61:cd:4d:b6:cc:a2:c5:ec:44:d1:e6:69:e5:
2b:85:05:74:a5:57:5c:09:3a:a7:40:d2:23:a7:b4:
2a:48:ed:3d:47:8a:c3:e9:10:c7:93:d2:9f:da:13:
f2:3c:ec:d0:0b:d0:ac:bd:cd:b7:0a:b1:f6:d5:e9:
82:1b:85:15:3f:39:81:f2:07:cf:5f:a2:0f:cd:f5:
e4:e4:32:b1:d3:fb:b3:b0:12:d7:d2:70:40:0d:5c:
67:c9:9a:ba:eb:2f:f3:c0:8e:5b:29:c8:07:b1:24:
3a:29:73:87:ff:06:44:3c:09:77:db:f2:f2:84:a9:
48:d4:5c:16:96:eb:a4:59:bf
e : 65537
Hint! Here is an example encryption :-
For m = 17 (integer), the encryption c = Enc(m) would be as follows :-
Integer :-
1135313888561729073213055678884572816699034138956362159587056821428036375159777212072
5436988986341387306079511224607415371455357387825108282422079151911468807886017426869
6096857915990814056511351498985054746953628660269153604131959421016678177032253587129
039122137054829046267874924979660429722673243620432019
Hex (Little Endian) :-
93d8c080cecba3b42e615118cb4598b39a76f74053ae23cb1e286eb397c6ba9c2b60e7217b9c30a9c8a83ab
ecf545df0647d17e9a5653e1b87b25efb49b7c6d2acce872aa8693673fb887a4d0d4505081946dfe32d320a2f
03e71f8d6c767ea9ab9efc9bc6e74aba5c4916043f6e697da12282762bb1f7b4b20c884e7a8faca1
You can use Python 3's from_bytes and to_bytes functions for integers to perform the encodings.
Penyelesaian
Kami diberikan layanan untuk dekripsi cipherteks pada server. Untuk mengungkap isi cipherteks maka bisa diselesaikan dengan LSB Oracle.
#!/usr/bin/python
import re
import libnum, decimal
from pwn import *
# from ./lsb_oracle.vmp.exe /pubkey
n = 0x00b961cd4db6cca2c5ec44d1e669e52b850574a5575c093aa740d223a7b42a48ed3d478ac3e910c793d29fda13f23cecd00bd0acbdcdb70ab1f6d5e9821b85153f3981f207cf5fa20fcdf5e4e432b1d3fbb3b012d7d270400d5c67c99abaeb2ff3c08e5b29c807b1243a297387ff06443c0977dbf2f284a948d45c1696eba459bf
e = 65537
# from description.py
c = 0x62e46a679ea85003b5d788ade93b618f25a965bf5761577de67362e2337452f63c42f53b34e422b699bfaa2abefe5d09ee9f74a1002238dcbb2ca8ac24723ad905726f372ba2bcaef603b23cde784113f3e589667203f8c504da803e80dfc05fb8e269acef8639ac406782628a1224a928aac5a9368caae90dabd9dff55eb7a0
def chunk(s, n):
return [s[i:i+n] for i in range(0, len(s), n)]
def to_litte_endian(c):
two = chunk(hex(c).replace('0x',''),2)
two.reverse()
res=''.join(two)
if len(res) % 2 != 0:
res += '0'
return res
def to_litte_endian_rev(c):
two = chunk(c,2)
two.reverse()
res=''.join(two)
if len(res) % 2 != 0:
res += '0'
return res
# Encrypt the plaintext integer 2
c_of_2 = pow(2,e,n)
# Run the oracle in wine. Works fine. Who needs windows.
# p = process(['wine','lsb_oracle.vmp.exe','/decrypt'])
# Ask the oracle for the LSB of a decryption of c
def oracle(c):
p = remote('128.199.224.175', 34000)
p.recv(4096)
# #print c
#print '++++++++++++++++++++++++++++'
#print to_litte_endian(c)
p.sendline(to_litte_endian(c))
dec = p.recv(4096)
#print '############################'
print 'dec', dec
try:
a = dec.decode('hex')
b = to_litte_endian_rev(dec).decode('hex')
except:
a = 'false'
b = 'false'
if 'pctf' in a or 'pctf' in b:
print a,b
5/0
#print '----------------------------'
decry = re.findall(r'\n([0-9a-f]+)\n', dec)[0]
#print 'decry', decry
#print '============================'
return int(to_litte_endian_rev(decry), 16)
# code from http://secgroup.dais.unive.it/wp-content/uploads/2012/11/Practical-Padding-Oracle-Attacks-on-RSA.html
# by Riccardo Focardi
def partial(c,n):
k = n.bit_length()
decimal.getcontext().prec = k # allows for 'precise enough' floats
lower = decimal.Decimal(0)
upper = decimal.Decimal(n)
for i in range(k):
possible_plaintext = (lower + upper)/2
if not oracle(c):
upper = possible_plaintext # plaintext is in the lower half
else:
lower = possible_plaintext # plaintext is in the upper half
c=(c*c_of_2) % n # multiply y by the encryption of 2 again
# By now, our plaintext is revealed!
return int(upper)
print "[*] Conducting Oracle attack..."
print repr(libnum.n2s(partial((c*c_of_2)%n,n)))