前言

LSB简介
  LSB全称为 Least Significant Bit（最低有效位），是一种常被用做图片隐写的算法（在CTF中经常见到她的身影）。LSB属于空域算法中的一种，是将信息嵌入到图像点中像素位的最低位，以保证嵌入的信息是不可见的，但是由于使用了图像不重要的像素位，算法的鲁棒性差，水印信息很容易为滤波、图像量化、几何变形的操作破坏。

算法分析
  PNG和BMP图片中的图像像素一般是有由RGB三原色组成（如图1所示），每一种颜色占用8位，取值范围为0x00~0xFF，既有2 24 2^{24}2 
24种色值。而人类的眼睛可以区分约1000万种不同的颜色，这就意味着人类眼睛无法区分的颜色还有600多万。

在密码学中，预言机被定义为某种“黑匣子”机制，它将泄漏有关输入上的加密操作的一些信息。对于特定输入，预言机的输出始终相同。因此，预言机可用于逐个了解明文，包括完整的明文恢复。

在我们的例子中，我们有一个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()