ssh 密钥交换细节和实现 diffie-hellman-group-exchange-sha
ssh的DH秘钥交换是一套复合几种算法的秘钥交换算法。在RFC4419中称为diffie-hellman-groupX-exchange-shaX 的算法(也有另一种单纯的 rsaX-shaX 交换算法)。本文就以diffie-hellman-group-exchange-sha256为例,详尽地讲解整个完整的秘钥交换过程。
笔者在RFC上和网上看了很久,也只是做了一个大致了解,对实现的帮助不大。实际在实现过程中,有太多的细节需要注意,在很多细节的分歧中,需要自己抱着勇气去测试。(原谅我不看openssh源码和使用openssl库,我只想全部自己实现整个ssh)。在diffie-hellman-group-exchange-sha256中,数据的类型非常地重要,因为涉及到hash运算,一定要区别好整数与字符串还有进制。一个小的不同都会导致hash的结果大不一样,hash错了以后的工作都是徒劳。
diffie-hellman-group-exchange-sha256的整个过程中一共要用到的秘钥交换算法有:diffie-hellman、sha256、ssh-rsa(或其他算法协商的host key,不是单纯的rsa,虾米告诉我ssh用的是RSASSA-PKCS1-v1_5 scheme标准)。而要支持这些加密算法,又需要很多基础算法:多进制大整数、高精度运算、快速模幂、离散算法...(还好自己有一定的acm基础,本来当初是打算学习并实现ssh协议,结果在算法的道路上越走越远,这次就当锻炼自己了。表示以后要好好运用面向对象技术,再也不实现不必要的底层了,以后涉及到安全传输就直接用openssl了)
以下为各个算法的讲解,先说最重要的几个基础数据结构与计算方法:
1、mpint: 二进制补码格式的多精度整数,储存为一个字符,每个字符8位,从高位到低位,负数最高位为1,正数最高位为0(只用到整数)。数据格式为:4字符长度+该长度字符的数值。例如:a1d8:00 00 00 03 00 a1 d8; 4:00 00 00 02 00 04
2、多进制大整数:平时以16进制存储,这样便于使用的时候少转化,转二进制也很快,实现很麻烦,我虽然有自己的大整数模板,但终归是不放心,我就用cryptopp自带的大整数改写过来用(人家可是用的汇编计算的)。
3、高精度运算:主要实现加法乘法和求余即可,因为dh和rsa只需要用到乘法与求余。
4、快速模幂:DH算法和RSA算法都会用到相似的运算:a^b%c 。因为b是一个大整数,因此对于他的幂运算我们将b进行二分,然后对a以及a计算后的结果进行计算,这样能省下大量不必要的运算。几个例子:3^8=3*3*3*3*3*3*3*3要进行7次运算。而这样化解(3^4)*(3^4)=(3^4)^2=((3^2)*(3^2))^2=((3^2)^2)^2只需要进行3次运算。第一种方式的时间复杂度是O(n),第二种二分幂的方法时间复杂度是O(logn),当b为10位十进制的整数时,第一种方式要计算10^10次,而用二分幂的方式只需要计算大约30多次。因为我们要求的是余果,所以在进行幂运算的同时就进行模运算,也能极大减少运算量,否则内存可能都装不下那么大的幂果。下面给出代码实现:
- Integer fastpower_comp(Integer a,Integer b,Integer c)
- {
- /*sample unused fast power
- Integer re=1;
- for(int i=0;i<b;i++)
- {
- re*=a;
- re%=c;
- }
- return re;
- */
- //fast power
- Integer n=c;
- c=1;
- while(b!=0)
- {
- if(b%2!=0)
- {
- b=b-1;
- c=(c*a)%n;
- }
- else
- {
- b=b/2;
- a=(a*a)%n;
- }
- }
- return c;
- }
密码算法:
1、diffie-hellman:
服务器首先产成两个数G、P,P为一个非常大的素数,作为DH算法的模;G为密码发生器,也就是P的一个原根(不理解没关系),服务器将这两个数发给客户端,用于秘钥的交换。
客户端生成一个数(客户端的私钥)x(0<x<P,但x应该大一点,否则当G特别小时生成的秘钥长度可能会很短,服务器会拒绝),计算e=(G^x)%P。得到的e就是客户端的公钥,客户端将e发送给服务器。
服务器也同客户端一样,生成一个数y,计算f=(G^y)%P。将服务器公钥f发送给客户端。
现在客户端与服务器都知道了对方的公钥,双方把对方的公钥作为自己模幂运算的底数进行运算,服务器计算K1=(e^y)%P,客户端计算K2=(f^x)%P 可以证明这里K1==K2 ,得到的K值便是双方所交换的秘钥。
大素数的生成:我采用了一种猜测加枚举的的方法。做过筛法算素数的都知道当数越大,出现连续素数的概率越高,而且连续的长度越长。我们可以通过随机生成一个大数(最好是奇数),然后判断该素数是否为素数,如果不是,将这个数加二再判断,直到判断为素数即可,以后每次再要取素数就可以把这个结果加再判断(此时素数的几率很高)。
- class m_dh
- {
- public:
- Integer dh_g,dh_p,dh_x,dh_e;
- Integer dh_y,dh_f;
- Integer dh_k;
- void set_g_and_p(const Integer g,const Integer p)
- {
- dh_g=g;
- dh_p=p;
- }
- void set_y(Integer y)
- {
- dh_y=y;
- }
- void set_f(Integer f)
- {
- dh_f=f;
- }
- void comp_e();
- Integer get_e()
- {
- return dh_e;
- }
- void comp_k();
- Integer get_k()
- {
- return dh_k;
- }
- };
- void m_dh::comp_e()
- {
- dh_x=mkrandomnum(50)+1;
- dh_e=fastpower_comp(dh_g,dh_x,dh_p);
- }
- void m_dh::comp_k()
- {
- dh_k=fastpower_comp(dh_f,dh_x,dh_p);
- }
2、rsa:
这里讲的是裸的rsa算法。
服务器生成两个不同的素数p和q,计算出模n=p*q,并计算欧拉函数φ(n) = (p-1)(q-1)。服务器再在1到φ(n) 之间生成一个与φ(n)互质的的数e找到另一个数d满足(e*d)%φ(n)==1。
现在服务器有三个数n、e、d ,ne的组合为rsa的公钥,nd为私钥。服务器将公钥发给客户端。在以后的加密解密中,公钥用于加密和签名验证,私钥用于解密与签名。
加密数字K:计算C=(K^e)%n,C即为加密后的数据 解密C得到K:K=(C^d)%n
签名采用相反的方式,即服务器用私钥加密,客户端用公钥解密,验证解密后的数据。
然而ssh-rsa使用的是 RSASSA-PKCS1-v1_5 scheme标准,他还含有一些其他的填充值,实际实现的时候需要考虑周全。
- class m_rsa
- {
- public:
- Integer rsa_e;
- Integer rsa_n;
- void set_e_and_n(Integer e,Integer n)
- {
- rsa_e=e;
- rsa_n=n;
- }
- Integer comp_rsa_result(Integer num);
- };
- Integer m_rsa::comp_rsa_result(Integer num)
- {
- return fastpower_comp(num,rsa_e,rsa_n);
- }
3、sha256
散列算法没什么可讲的,主要注意sha256的密文长度是64位的16进制,在进行rsa加解密以及计算sessionid的时候一定要注意关于长度的问题。使用的重点在于需要哪些值以什么样的一种组合方式去参与hash运算。
我就直接使用cryptopp的hash算法实现了:
- class m_sha
- {
- public:
- string encode_sha1(string data);
- string encode_sha256(string data);
- };
- string m_sha::encode_sha256(string data)
- {
- string hash;
- SHA256 sha256;
- HashFilter hash_filter (sha256);
- hash_filter.Attach(new HexEncoder(new StringSink(hash), false));
- hash_filter.Put((byte *)data.c_str(),data.length());
- hash_filter.MessageEnd();
- return hash;
- }
详细过程:
基本的算法了解了就可以来看diffie-hellman-group-exchange-sha256的整个过程了。
整个交换过程有5个数据包:按顺序分别是1、dh key exchange init;2、dh key exchange reply;3、dh gex init 4、dhgex reply 5、new keys
1、dh key exchange init(30)
客户端告诉服务器开始DH交换。
2、dh key exchange reply(31)
服务器将生成的P和G发给客户端。
3、dh gex init(32)
客户端收到服务器发过来的P和G后,自己计算出e返回给客户端
4、dh gex reply(33)
服务器收到客户端的e后,根据算法计算出秘钥值K。然后使用sha256算法将一些已知信息hash加密为H(具体过程后面会提到),并用rsa将hash值签名。最后发送rsa的公钥、dh的f值、rsa签名后的hash信息发回客户端。
5、new keys(21)
客户端根据服务器发回的f计算出同样的k值,并根据同样的已有信息hash计算得到H后使用服务器发来的rsa公钥校验服务器发回的hash值的签名,根据得到的hash值H即会话用的session_id,再进行特定的hash运算(参见下文)即可得到以后用于数据加密的秘钥。如果校验无误,返回new key(21),表示秘钥交换的过程完毕,以后的数据都将由所得秘钥进行加密。
H与session_id的计算:
H=hash(V_C||V_S||I_C||I_S||K_S||e||f||K);
按顺序用到的值(注意类型):
类型 | 值 | 说明 |
string | V_C | 客户端的初始报文(版本信息:SSH-2.0-xxx,不含结尾的CR和LF) |
string | V_S | 服务器的初始报文 |
string | I_C | 客户端 SSH_MSG_KEX_INIT的有效载荷(不含开头的数据长度值) |
string | I_S | 服务器的同上 |
string | K_S | 主机秘钥(dh gex reply(33)过程服务器发送host key (RSA公钥)) |
mpint | e | 客户端DH公钥 |
mpint | f | 服务器DH公钥 |
mpint | K | 共同DH计算结果 |
将以上内容按顺序进行拼接,不要夹杂或尾随多余字符。将拼接后的字符串进行sha256计算出结果H。这个H就是session_id(会话第一次的秘钥交换生成的的H才是session_id,以后如果还要进行秘钥交换,session_id不会改变)。
加密秘钥计算:
这里的加密秘钥指的是以后数据通信所用的秘钥,一般用aes算法。
计算方式:hash(K,H,单个字符,session_id);
单个字符指的是单个大写的ASCII字母,根据不同的加密秘钥选择不同的字符来计算。
字母 | 秘钥 |
'A' | 客户端到服务器的初始IV(CBC) |
'B' | 服务器到客户端的初始IV |
'C' | 客户端到服务器的加密秘钥(数据加解密秘钥) |
'D' | 服务器到客户端的加密秘钥 |
'E' | 客户端到服务器的完整性秘钥(HMAC) |
'F' | 服务器到客户端的完整性秘钥 |
哈希计算得到字符串RE,如果我么想要的秘钥长度比RE长,则在RE后面继续加上一个hash值:hash(K,H,RE)成为一个加长的RE。还不够继续加上hash(K,H,RE),依次类推
ssh秘钥交换的过程就告一段落了。笔者在网上找不到合适资料,尤其是这些关于diffie-hellman-group-exchange-sha 的很多细节,自己苦逼了很长时间(本来打算两下撸完去学其他的)终于完成了了。希望给想要自己实现该算法的朋友给予帮助。如还遇到其他的问题可Q我(WCHRT)。
推荐阅读
-
如何在Linux上设置SSH密钥和别名以实现无需密码的登录
-
ssh工作流程及原理-SSH(Secure Shell Protocol,安全的壳程序协议),它可以通过数据包加密技术将等待传输的数据包加密后再传输到网络上。ssh协议本身提供两个服务器功能:一个是类似telnet的远程连接使用shell的服务器;另一个就是类似ftp服务的sftp-server,提供更安全的ftp服务。 连接加密技术简介 目前常见的网络数据包加密技术通常是通过“非对称密钥系统”来处理的。主要通过两把不一样的公钥与私钥来进行加密与解密的过程。 公钥(public key):提供给远程主机进行数据加密的行为,所有人都可获得你的公钥来将数据加密。 私钥(private key):远程主机使用你的公钥加密的数据,在本地端就能够使用私钥来进行解密。私钥只有自己拥有。 SSH工作过程:在整个通讯过程中,为实现SSH的安全连接,服务端与客户端要经历如下五个阶段: 版本号协商阶段 SSH目前包括SSH1和SSH2两个版本,双方通过版本协商确定使用的版本 密钥和算法协商阶段 SSH支持多种加密算法,双方根据本端和对端支持的算法,协商出最终使用的算法 认证阶段 SSH客户端向服务器端发起认证请求,服务器端对客户端进行认证 会话请求阶段 认证通过后,客户端向服务器端发送会话请求 交互会话阶段 会话请求通过后,服务器端和客户端进行信息的交互 一、版本协商阶段 服务器端打开端口22,等待客户端连接; 客户端向服务器端发起TCP初始连接请求,TCP连接建立后,服务器向客户端发送第一个报文,包括版本标志字符串,格式为“SSH-<主协议版本号>.<次协议版本号>.<软件版本号>”,协议版本号由主版本号和次版本号组成,软件版本号主要是为调试使用。 客户端收到报文后,解析该数据包,如果服务器的协议版本号比自己的低,且客户端能支持服务器端的低版本,就使用服务器端的低版本协议号,否则使用自己的协议版本号。 客户端回应服务器一个报文,包含了客户端决定使用的协议版本号。服务器比较客户端发来的版本号,决定是否能同客户端一起工作。如果协商成功,则进入密钥和算法协商阶段,否则服务器断开TCP连接。 说明:上述报文都是采用明文方式传输。 二、密钥和算法协商阶段 服务器端和客户端分别发送算法协商报文给对端,报文中包含自己支持的公钥算法列表、加密算法列表、MAC(Message Authentication Code,消息验证码)算法列表、压缩算法列表等等。 服务器端和客户端根据对端和本端支持的算法列表得出最终使用的算法。 服务器端和客户端利用DH交换(Diffie-Hellman Exchange)算法、主机密钥对等参数,生成会话密钥和会话ID。 由此,服务器端和客户端就取得了相同的会话密钥和会话ID。对于后续传输的数据,两端都会使用会话密钥进行加密和解密,保证了数据传送的安全。在认证阶段,两端会使用会话用于认证过程。 会话密钥的生成: 客户端需要使用适当的客户端程序来请求连接服务器,服务器将服务器的公钥发送给客户端。(服务器的公钥产生过程:服务器每次启动sshd服务时,该服务会主动去找/etc/ssh/ssh_host*文件,若系统刚装完,由于没有这些公钥文件,因此sshd会主动去计算出这些需要的公钥文件,同时也会计算出服务器自己所需要的私钥文件。) 服务器生成会话ID,并将会话ID发给客户端。 若客户端第一次连接到此服务器,则会将服务器的公钥数据记录到客户端的用户主目录内的~/.ssh/known_hosts。若是已经记录过该服务器的公钥数据,则客户端会去比对此次接收到的与之前的记录是否有差异。客户端生成会话密钥,并用服务器的公钥加密后,发送给服务器。 ****服务器用自己的私钥将收到的数据解密,获得会话密钥。 服务器和客户端都知道了会话密钥,以后的传输都将被会话密钥加密。 三、认证阶段 SSH提供两种认证方法: 基于口令的认证(password认证):客户端向服务器发出password认证请求,将用户名和密码加密后发送给服务器,服务器将该信息解密后得到用户名和密码的明文,与设备上保存的用户名和密码进行比较,并返回认证成功或失败消息。 基于密钥的认证(publickey认证):客户端产生一对公共密钥,将公钥保存到将要登录的服务器上的那个账号的家目录的.ssh/authorized_keys文件中。认证阶段:客户端首先将公钥传给服务器端。服务器端收到公钥后会与本地该账号家目录下的authorized_keys中的公钥进行对比,如果不相同,则认证失败;否则服务端生成一段随机字符串,并先后用客户端公钥和会话密钥对其加密,发送给客户端。客户端收到后将解密后的随机字符串用会话密钥发送给服务器。如果发回的字符串与服务器端之前生成的一样,则认证通过,否则,认证失败。 注:服务器端对客户端进行认证,如果认证失败,则向客户端发送认证失败消息,其中包含可以再次认证的方法列表。客户端从认证方法列表中选取一种认证方法再次进行认证,该过程反复进行。直到认证成功或者认证次数达到上限,服务器关闭连接为止。实例
-
SSH 协议理论解释 - SSH 传输层协议 - 主要用于 SSH 版本协商、算法协商和密钥交换
-
ssh 密钥交换细节和实现 diffie-hellman-group-exchange-sha
-
windows下进程间通信的(13种方法)-摘 要 本文讨论了进程间通信与应用程序间通信的含义及相应的实现技术,并对这些技术的原理、特性等进行了深入的分析和比较。 ---- 关键词 信号 管道 消息队列 共享存储段 信号灯 远程过程调用 Socket套接字 MQSeries 1 引言 ---- 进程间通信的主要目的是实现同一计算机系统内部的相互协作的进程之间的数据共享与信息交换,由于这些进程处于同一软件和硬件环境下,利用操作系统提供的的编程接口,用户可以方便地在程序中实现这种通信;应用程序间通信的主要目的是实现不同计算机系统中的相互协作的应用程序之间的数据共享与信息交换,由于应用程序分别运行在不同计算机系统中,它们之间要通过网络之间的协议才能实现数据共享与信息交换。进程间通信和应用程序间通信及相应的实现技术有许多相同之处,也各有自己的特色。即使是同一类型的通信也有多种的实现方法,以适应不同情况的需要。 ---- 为了充分认识和掌握这两种通信及相应的实现技术,本文将就以下几个方面对这两种通信进行深入的讨论:问题的由来、解决问题的策略和方法、每种方法的工作原理和实现、每种实现方法的特点和适用的范围等。 2 进程间的通信及其实现技术 ---- 用户提交给计算机的任务最终都是通过一个个的进程来完成的。在一组并发进程中的任何两个进程之间,如果都不存在公共变量,则称该组进程为不相交的。在不相交的进程组中,每个进程都独立于其它进程,它的运行环境与顺序程序一样,而且它的运行环境也不为别的进程所改变。运行的结果是确定的,不会发生与时间相关的错误。 ---- 但是,在实际中,并发进程的各个进程之间并不是完全互相独立的,它们之间往往存在着相互制约的关系。进程之间的相互制约关系表现为两种方式: ---- (1) 间接相互制约:共享CPU ---- (2) 直接相互制约:竞争和协作 ---- 竞争——进程对共享资源的竞争。为保证进程互斥地访问共享资源,各进程必须互斥地进入各自的临界段。 ---- 协作——进程之间交换数据。为完成一个共同任务而同时运行的一组进程称为同组进程,它们之间必须交换数据,以达到协作完成任务的目的,交换数据可以通知对方可以做某事或者委托对方做某事。 ---- 共享CPU问题由操作系统的进程调度来实现,进程间的竞争和协作由进程间的通信来完成。进程间的通信一般由操作系统提供编程接口,由程序员在程序中实现。UNIX在这个方面可以说最具特色,它提供了一整套进程间的数据共享与信息交换的处理方法——进程通信机制(IPC)。因此,我们就以UNIX为例来分析进程间通信的各种实现技术。 ---- 在UNIX中,文件(File)、信号(Signal)、无名管道(Unnamed Pipes)、有名管道(FIFOs)是传统IPC功能;新的IPC功能包括消息队列(Message queues)、共享存储段(Shared memory segment)和信号灯(Semapores)。 ---- (1) 信号 ---- 信号机制是UNIX为进程中断处理而设置的。它只是一组预定义的值,因此不能用于信息交换,仅用于进程中断控制。例如在发生浮点错、非法内存访问、执行无效指令、某些按键(如ctrl-c、del等)等都会产生一个信号,操作系统就会调用有关的系统调用或用户定义的处理过程来处理。 ---- 信号处理的系统调用是signal,调用形式是: ---- signal(signalno,action) ---- 其中,signalno是规定信号编号的值,action指明当特定的信号发生时所执行的动作。 ---- (2) 无名管道和有名管道 ---- 无名管道实际上是内存中的一个临时存储区,它由系统安全控制,并且独立于创建它的进程的内存区。管道对数据采用先进先出方式管理,并严格按顺序操作,例如不能对管道进行搜索,管道中的信息只能读一次。 ---- 无名管道只能用于两个相互协作的进程之间的通信,并且访问无名管道的进程必须有共同的祖先。 ---- 系统提供了许多标准管道库函数,如: pipe——打开一个可以读写的管道; close——关闭相应的管道; read——从管道中读取字符; write——向管道中写入字符; ---- 有名管道的操作和无名管道类似,不同的地方在于使用有名管道的进程不需要具有共同的祖先,其它进程,只要知道该管道的名字,就可以访问它。管道非常适合进程之间快速交换信息。 ---- (3) 消息队列(MQ) ---- 消息队列是内存中独立于生成它的进程的一段存储区,一旦创建消息队列,任何进程,只要具有正确的的访问权限,都可以访问消息队列,消息队列非常适合于在进程间交换短信息。 ---- 消息队列的每条消息由类型编号来分类,这样接收进程可以选择读取特定的消息类型——这一点与管道不同。消息队列在创建后将一直存在,直到使用msgctl系统调用或iqcrm -q命令删除它为止。 ---- 系统提供了许多有关创建、使用和管理消息队列的系统调用,如: ---- int msgget(key,flag)——创建一个具有flag权限的MQ及其相应的结构,并返回一个唯一的正整数msqid(MQ的标识符); ---- int msgsnd(msqid,msgp,msgsz,msgtyp,flag)——向队列中发送信息; ---- int msgrcv(msqid,cmd,buf)——从队列中接收信息; ---- int msgctl(msqid,cmd,buf)——对MQ的控制操作; ---- (4) 共享存储段(SM) ---- 共享存储段是主存的一部分,它由一个或多个独立的进程共享。各进程的数据段与共享存储段相关联,对每个进程来说,共享存储段有不同的虚拟地址。系统提供的有关SM的系统调用有: ---- int shmget(key,size,flag)——创建大小为size的SM段,其相应的数据结构名为key,并返回共享内存区的标识符shmid; ---- char shmat(shmid,address,flag)——将当前进程数据段的地址赋给shmget所返回的名为shmid的SM段; ---- int shmdr(address)——从进程地址空间删除SM段; ---- int shmctl (shmid,cmd,buf)——对SM的控制操作; ---- SM的大小只受主存限制,SM段的访问及进程间的信息交换可以通过同步读写来完成。同步通常由信号灯来实现。SM非常适合进程之间大量数据的共享。 ---- (5) 信号灯 ---- 在UNIX中,信号灯是一组进程共享的数据结构,当几个进程竞争同一资源时(文件、共享内存或消息队列等),它们的操作便由信号灯来同步,以防止互相干扰。 ---- 信号灯保证了某一时刻只有一个进程访问某一临界资源,所有请求该资源的其它进程都将被挂起,一旦该资源得到释放,系统才允许其它进程访问该资源。信号灯通常配对使用,以便实现资源的加锁和解锁。 ---- 进程间通信的实现技术的特点是:操作系统提供实现机制和编程接口,由用户在程序中实现,保证进程间可以进行快速的信息交换和大量数据的共享。但是,上述方式主要适合在同一台计算机系统内部的进程之间的通信。 3 应用程序间的通信及其实现技术 ---- 同进程之间的相互制约一样,不同的应用程序之间也存在竞争和协作的关系。UNIX操作系统也提供一些可用于应用程序之间实现数据共享与信息交换的编程接口,程序员可以通过自己编程来实现。如远程过程调用和基于TCP/IP协议的套接字(Socket)编程。但是,相对普通程序员来说,它们涉及的技术比较深,编程也比较复杂,实现起来困难较大。 ---- 于是,一种新的技术应运而生——通过将有关通信的细节完全掩盖在某个独立软件内部,即底层的通讯工作和相应的维护管理工作由该软件内部来实现,用户只需要将通信任务提交给该软件去完成,而不必理会它的具体工作过程——这就是所谓的中间件技术。 ---- 我们在这里分别讨论这三种常用的应用程序间通信的实现技术——远程过程调用、会话编程技术和MQSeries消息队列技术。其中远程过程调用和会话编程属于比较低级的方式,程序员参与的程度较深,而MQSeries消息队列则属于比较高级的方式,即中间件方式,程序员参与的程度较浅。 ---- 4.1 远程过程调用(RPC)