前言
在密码学中，预言机被定义为某种“黑匣子”机制，它将泄漏有关输入上的加密操作的一些信息。对于特定输入，预言机的输出始终相同。因此，预言机可用于逐个了解明文，包括完整的明文恢复。
在我们的例子中，我们有一个LSB预言机。在这种情况下，对于每个输入密文，预言机将使用其私钥对其进行解密，然后通知我们解密明文的单个最低有效位。在这种情况下，最低有效位将告诉我们结果数字是奇数还是偶数。这也被称为“奇偶校验侧信道攻击”，我从里卡尔多·福卡尔迪（Riccardo Focardi）的这篇论文中了解到所有内容，你可以在这里阅读。请记住，在RSA数学中，我们的明文和密文只是长整数。我们将它们转换为字符串以对我们有用，但在下面当我谈论明文或密文数学时，我只是指那些长整数的数学。
在这个挑战中，我们的LSB预言机二进制文件将给我们一个如果我们的标志明文是奇数的，如果我们的标志明文是偶数，则给我们一个''。我们可以通过使用我们的公钥加密数字 2（偶数）来确认这一点。
一、lsb-oracle
1.打开题目
2.解题
2.1 补充缺失文件和包
打开题目得到description.py和lsb_oracle.vmp.exe文件
题目有问题缺少description.py
#! /usr/bin/env python3
from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long
n = -1 # get it from the provided EXE file
e = -1 # get it from the provided EXE file
flag = b'' # redacted
key = RSA.construct((n, e))
cipher = PKCS1_v1_5.new(key)
ctxt = bytes_to_long(cipher.encrypt(flag))
print(ctxt)
# output is:
# 2201077887205099886799419505257984908140690335465327695978150425602737431754769971309809434546937184700758848191008699273369652758836177602723960420562062515168299835193154932988833308912059796574355781073624762083196012981428684386588839182461902362533633141657081892129830969230482783192049720588548332813
linux下需要安装wine来运行exe文件
sudo apt-get install wine
2.2 破密脚本
solve.py
#!/usr/bin/python
import libnum, decimal
from pwn import *
# from ./lsb_oracle.vmp.exe /pubkey
n = 120357855677795403326899325832599223460081551820351966764960386843755808156627131345464795713923271678835256422889567749230248389850643801263972231981347496433824450373318688699355320061986161918732508402417281836789242987168090513784426195519707785324458125521673657185406738054328228404365636320530340758959
e = 65537
# from description.py
c = 2201077887205099886799419505257984908140690335465327695978150425602737431754769971309809434546937184700758848191008699273369652758836177602723960420562062515168299835193154932988833308912059796574355781073624762083196012981428684386588839182461902362533633141657081892129830969230482783192049720588548332813
# 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'])
print "[*] Starting wine and LSB Oracle..."
p.recvlines(4)
# Ask the oracle for the LSB of a decryption of c
def oracle(c):
p.sendline(str(c))
return int(p.recvlines(2)[0])
# 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)))
2.3 运行解密
使用Wine来执行oracle二进制文件
python solve.py
得到flag：
root@kali:~/sharif16/lsboracle# ./solve.py
[+] Starting program '/usr/bin/wine': Done
[*] Starting wine and LSB Oracle...
[*] Conducting Oracle attack...
'\x02\xa9\x12\xa7uA\x94\x8e\x8c2\xd5(\xda\x1eq?\xf7\xd0TL\xe8\xde1$\xbf\xe4w\xe1\x18\x12\x1f\xef\x03\x8b{\x7f\xb2\x9c\xa6Bs\xd2\xfe&\xe8+k7\xd8\xe7\xa5\x0b\xaf\xa8R\x12\x93\x0e,\xdfp\xff\x9a\xe7\x9b\xbduN4\x85I\xde3\x07\xb2n\xa4\xdb"\xd5\xfaf\x84\x00SharifCTF{65d7551577a6a613c99c2b4023039b0a}'
备注
windows脚本如下
from subprocess import Popen, PIPE
from Crypto.Util.number import long_to_bytes
def oracle(ciphertext):
print("sent ciphertext " + str(ciphertext))
p = Popen(['lsb_oracle.vmp.exe', '/decrypt'], stdout=PIPE, stdin=PIPE, stderr=PIPE)
result = p.communicate(str(ciphertext) + "\n-1")
lsb = int(result[0][97])
print(lsb, result)
return lsb
def brute_flag(encrypted_flag, n, e, oracle_fun):
flag_count = n_count = 1
flag_lower_bound = 0
flag_upper_bound = n
ciphertext = encrypted_flag
mult = 1
while flag_upper_bound > flag_lower_bound + 1:
ciphertext = (ciphertext * pow(2, e, n)) % n
flag_count *= 2
n_count = n_count * 2 - 1
print("upper = %d" % flag_upper_bound)
print("upper flag = %s" % long_to_bytes(flag_upper_bound))
print("lower = %d" % flag_lower_bound)
print("lower flag = %s" % long_to_bytes(flag_lower_bound))
print("bit = %d" % mult)
mult += 1
if oracle_fun(ciphertext) == 0:
flag_upper_bound = n * n_count / flag_count
else:
flag_lower_bound = n * n_count / flag_count
n_count += 1
return flag_upper_bound
def main():
n = 120357855677795403326899325832599223460081551820351966764960386843755808156627131345464795713923271678835256422889567749230248389850643801263972231981347496433824450373318688699355320061986161918732508402417281836789242987168090513784426195519707785324458125521673657185406738054328228404365636320530340758959
ct = 2201077887205099886799419505257984908140690335465327695978150425602737431754769971309809434546937184700758848191008699273369652758836177602723960420562062515168299835193154932988833308912059796574355781073624762083196012981428684386588839182461902362533633141657081892129830969230482783192049720588548332813
print(long_to_bytes(brute_flag(ct, n, 65537, oracle)))
main()
