Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Another mechanism to achieve Forward Security, without changing the protocol #178

Open
RPRX opened this issue Jan 5, 2021 · 34 comments
Open

Comments

@RPRX
Copy link

RPRX commented Jan 5, 2021

For the record, I have designed the VLESS and XTLS protocols, and I started the Xray-core project a month or so ago.
So those involved in the discussion should have basic level of knowledge of protocol design, engineering practices, etc.

Here's another idea after #177. It can solve existing problem without changing the protocol, but have one limitation. Note that none of my designs require the introduction of additional long-term channels or bring in identifiable features, which is the basic guideline.

  1. On initial configuration, the server generates the random key, along with a corresponding timestamp.
  2. newkey = hash(oldkey), with updated timestamp, regularly, e.g. hourly. The old key should not be retained.
  3. This requires the same time on both sides. And it's not recommended for multiple clients to share key.

In addition, if the configuration is immediately imported to the user's client, actually the timestamp can be ignored during the import, thus eliminating the need to synchronize the time.

@RPRX
Copy link
Author

RPRX commented Jan 5, 2021

After further thought, update:

It is not necessary to sync time on both sides in most scenarios, which is not an actual limitation.

The server just needs to generate different keys for each device, which is very easy to do.

So I think this is the best solution at this stage based on current SS protocol.

@RPRX
Copy link
Author

RPRX commented Jan 5, 2021

It's built on top of the protocol, without introduction of additional long-term channels or bring in potential identifiable features.

cc @fortuna

@RPRX
Copy link
Author

RPRX commented Jan 5, 2021

@Mygod I would like to ask your explanation on the downvote. I expect a technical discussion rather than some cold violence.

@RPRX
Copy link
Author

RPRX commented Jan 5, 2021

@Mygod I would like to REQUEST your explanation on the downvote. I expect a technical discussion rather than some cold violence.

@fortuna
Copy link
Contributor

fortuna commented Jan 5, 2021

How does this provide forward-secrecy? If the attacker gets the key, they can decrypt all the recorded traffic by hashing the key with the timestamp of the traffic. Did I miss something?

@QuantumGhost
Copy link

As I have suggested in #177 (comment), you can first implement it as a shadowsocks plugin.

@RPRX
Copy link
Author

RPRX commented Jan 6, 2021

@fortuna

There is an obvious misunderstanding, I'll explain this mechanism in detail:

  1. key = hash(key) means that key itself will be updated, and the old key will no longer exists after few minutes / an hour.
  2. There's actually no main key, all keys' temporary and will be destroyed.
  3. Timestamp is not involved when hashing, just a record of time, making sure that software knows when to update key, and device will not lose state after shutting down for a long time. (by circulating time intervals then do hashing at startup)

Even if the attacker gets the current key, he can not revert hash to get previous keys, that's how this provides Forward Secrecy.

@RPRX
Copy link
Author

RPRX commented Jan 6, 2021

@QuantumGhost

Thanks for your advice. But seems it's not necessary to thumb down my design at first, which is very impolite that everybody can tell.

@RPRX
Copy link
Author

RPRX commented Jan 6, 2021

@fortuna

Here's an Academic Explanation

In short, this simple mechanism provides:

  1. Synchronized status, without extra communication. (so this doesn't require protocol change or additional long-term channels)
  2. Calculate the same key independently, like D-H key exchange achieved.
  3. Irreversible rollout of temporary keys, which is the key point to achieve Forward Secrecy.

@wevsty
Copy link

wevsty commented Jan 6, 2021

I recommend first reading https://shadowsocks.org/en/wiki/AEAD-Ciphers.html

The current protocol uses an encryption key for each connection that I call SessionKey (or subkey in the documentation).

SessionKey = HKDF_SHA1(main_key, salt, info) 

The main key is defined by the user.
Salt is randomly generated by the client.
info fixed string as ss-subkey.

In this design, even if a single SessionKey is leaked, the other session is still secure.

Adding a timestamp I don't think guarantees forward security.
If the attacker can know the mian key, the session key can be deduced after adding the timestamp to uncover the traffic.

Adding a timestamp only stops a portion of replay attacks.
Here's a research report:
English version: https://gfw.report/talks/imc20/en/
Chinese version: https://gfw.report/talks/imc20/zh/

I quote from it.

And as you can see, for first replays anyway at least around 25 percent of replay probes come within one second, so almost immediately

Nearly 25% of the replayed attacks were completed in almost a few seconds.Timestamps don't help us distinguish between these replay attacks.
So I don't think adding timestamps is useful at the moment.

@zonyitoo
Copy link
Contributor

zonyitoo commented Jan 6, 2021

A short conclusion for implementors: the key will be changed in a fixed period for both clients and servers with a pre-defined hash function. Am I right?

@RPRX
Copy link
Author

RPRX commented Jan 6, 2021

@zonyitoo y

@RPRX
Copy link
Author

RPRX commented Jan 6, 2021

@DuckSoft
Copy link

DuckSoft commented Jan 6, 2021

To my understanding, this plan is used to ensure the forward secrecy on a preshared key (PSK) leakage.
The preshared key is at first delivered in a secure channel by the server, and locally the key is stored along with timestamp.
During the communication, the preshared key is refreshed periodically according to some time slice (like one hour), and OVERWRITE THE OLD KEY WITH NEW KEY AND NEW TIMESTAMP, SO THAT THE PREVIOUS KEYS ARE NEVER KEPT LOCALLY.
This way when the key is compromised, since hash is hardly reversible, the attacker can hardly derive previous preshared keys, thus ensuring a forward secrecy.

Am I correct? @RPRX

@RPRX
Copy link
Author

RPRX commented Jan 6, 2021

@DuckSoft y

As for this guy @wevsty , seems he doesn't know "what's Forward Secrecy" at all, and totally misunderstands my design. Oh god.

@RPRX
Copy link
Author

RPRX commented Jan 6, 2021

To aviod misunderstanding, new expression: newkey = hash(oldkey)

@RPRX
Copy link
Author

RPRX commented Jan 6, 2021

@wevsty

精彩,你再次通过错误认知(误解读)推出了错误结论,即便正上方就是我详细的补充描述。

相信现在你已经了解了 前向保密 的定义,并发现了自己评论的内容完全存在误解且偏离主题。为了不误导他人,建议删掉。

@RPRX
Copy link
Author

RPRX commented Jan 6, 2021

@wevsty

另外,如果你感兴趣的话,我可以向你详细说明一下,你在 #177 中的一些说法有多么 误解读 与 无知。

而这里这个方案,我在开头已经明确建议了,段位不够的人不要掺和,没想到你还是来了,并且再次展示了自己的智商。

@wevsty
Copy link

wevsty commented Jan 6, 2021

As for this guy @wevsty , seems he doesn't know "what's Forward Secrecy" at all, and totally misunderstands my design. Oh god.

I know what is forward secrecy. Thank you for your concern.

你再次通过错误认知(误解读)推出了错误结论

A standard should be written with a specific implementation plan and be repeatable in practice.
If a standard is ambiguous it means that the standard should be revised.

而这里这个方案,我在开头已经明确建议了,段位不够的人不要掺和,没想到你还是来了,并且再次展示了自己的智商。

This is clearly a personal attack, and while I won't ask for an apology, you'd better stop this behavior.

Going back to the program, I think a lot of people have developed some different ideas.

So in response to the added content I'll restate my view.

If the preshared key (PSK) is only changed at regular intervals, then this behavior is not part of the protocol.
If you want to integrate into the protocol, please come up with a more detailed proposal and description.

@RPRX
Copy link
Author

RPRX commented Jan 6, 2021

@wevsty

Wonderful speech. Actually I didn't mean to target any person, as I will say exactly the same words if someone doesn't have patience to read the detailed description that I've already given but draw a totally wrong conclusion by just seeing timestamp.

The fact is that here's a pre-discussion before the official standard of my design, and I just post my idea, as you can notice.
So I think it's fair to require participants to have professional knowledge and inspiration to understand my mind.

Thus, if someone can not understand my idea or feels strange, it would be better to throw a question or just watch rather than negate my idea directly by a lot of words (as there's a strong possibility of misunderstanding at first).

I agree that more detailed standard is required, but it's not my fault that you ignored the previous detailed description about my idea and joined this pre-discussion with your misunderstanding. Please be patient in future discussions.

Going back to the program, it's not surprised if there are different ideas (though I didn't find many).

I think my idea will be the best:
Very easy to implement, without introduction of additional long-term channels or bring in potential identifiable features.

Feel free to introduce any better ideas.

@dev4u
Copy link

dev4u commented Jan 6, 2021

楼主应该专心去把你的想法实现出来、并完善,而不该在这里打嘴炮,不是吗?
诚然每个人都会、也可以认为自己才是最好的,但完全没必要强求别人也认同。这种揽炒做事风格,真不应该出现在这。
讨论事情要拿出讨论的态度,别动不动标榜自己如何出色、厉害。语气放平和,心态端正了,自然会在讨论中碰出闪光。

@RPRX
Copy link
Author

RPRX commented Jan 6, 2021

@dev4u

麻烦不要 断章取义,如果你没看明白发生了什么,或者你只看到了标粗的那两行。

诚然每个人都会、也可以认为自己才是最好的,但完全没必要强求别人也认同。这种揽炒做事风格,真不应该出现在这。

我并没有强求谁的认同,任何人完全可以不认同,合理的解释或更好的想法均可,但绝对不是乱踩或基于误解的否定。

况且当我说出上一个想法 #177 时,我完全没有说其它事情,后来我只是想简单表明我不会犯低级错误。

Besides, 实现我的想法与讨论我的想法是可以 并行 的。不要把讨论往 off-topic 的方向带

@RPRX
Copy link
Author

RPRX commented Jan 6, 2021

@dev4u

需要声明,我是希望参与讨论的人有相应的知识或实践过,探讨起来就会轻松很多,避免鸡同鸭讲,这样效率很低

比如只要编写过代理软件,就可以迅速判断出一个想法是否可实践,以及有无工程上的潜在优化方案

也就是说参与讨论的目标群体本来就不是所有人,这个我在一开始就标明了,而且这也是实践中很常见的做法

@fortuna
Copy link
Contributor

fortuna commented Jan 8, 2021

@RPRX Let me see if I understood correctly.

You are proposing a sequence of keys k_1, k_2, k_3, ..., k_n.
You first exchange k_1, then the client and server derives k_i = hash(k_(i-1)) on a schedule. Is that right?

Forward secrecy says that session keys will not be compromised even if long-term secrets used in the session key exchange are compromised.

Your proposal doesn't seem to have that property. If the long-term secret k_i gets compromised, the attacker can derive any k_j, j>=i and decrypt all sessions since k_i.

@DuckSoft throwing away the key has no impact on defining forward secrecy, since you could still compromise the key by other means (e.g. a dictionary attack, brute force or some vulnerability on how you generate them)

@DuckSoft
Copy link

DuckSoft commented Jan 8, 2021

@fortuna I see your point. You are correct but in the proposed method @RPRX mentioned a strong hypothesis: The old key should not be retained. If we accept that, there is somewhat no "long-term" secrets. The longest-term secret you can find is the key stored in clients/servers when it is compromised.

I am an amateur on this, but my intuition tells that maybe the noun "forward secrecy" is not understood the same among us. I noticed that in the definition, there is also a phrase says long-term secrets "used in the session key exchange", while in the proposed method, the only key exchange from the very beginning is assumed as secure, and there's actually no session key exchange afterwards. I doubt whether we should or can classify this method as forward secure or not.

Anyway, thanks @RPRX for sharing with us the interesting idea.

@RPRX
Copy link
Author

RPRX commented Jan 8, 2021

@fortuna

You are proposing a sequence of keys k_1, k_2, k_3, ..., k_n.
You first exchange k_1, then the client and server derives k_i = hash(k_(i-1)) on a schedule. Is that right?

Correct.

Forward secrecy says that session keys will not be compromised even if long-term secrets used in the session key exchange are compromised.

Your proposal doesn't seem to have that property. If the long-term secret k_i gets compromised, the attacker can derive any k_j, j>=i and decrypt all sessions since k_i.

Not correct.

First, actually there's no long-term secrets, all keys are temporary , it's the objective fact.

Second, on a trusted device, there's no possibility that k_(i-1) gets compromised before k_i if you do not store k_(i-1) anymore.
Anyone gets your device in the future will just get k_n at most.

If k_i gets compromised and you continue using this key, then it's a problem that even TLS has not solved yet (MITM attack).

since you could still compromise the key by other means (e.g. a dictionary attack, brute force or some vulnerability on how you generate them)

Not a problem if we choose the proper method/multi-processes.

  1. There are many ways to protect against dictionary attacks, such as adding hashed salt.
  2. Note that cracking hash means generating the same hash successfully. Restoring the original text is almost impossible.
  3. If someone gets unlimited computing power in the future, then nothing is safe anymore.

@RPRX
Copy link
Author

RPRX commented Jan 8, 2021

@fortuna

On the other hand, if this ever-changing key is considered the long-term key, then indeed we achieved the goal of forward secrecy: protects past sessions against future compromises of keys or passwords.

I agree that we should be clear about what are we doing here.

@RPRX
Copy link
Author

RPRX commented Jan 8, 2021

Blocked @QuantumGhost

说一下原因,这个人的行为一直是对我的观点按 thumbs down,并对相反的观点按 thumbs up
#177 到这里一直是这样,无论两边的观点本身如何,且他无法给出适当的理由

只能眼不见为净了。

@xiaokangwang
Copy link

我说一下我的分析吧,这个密钥滚动机制可以保证服务器和客户端保证不复用密码,如果在某个时间点之后被入侵,而之前一直保证安全,且可以彻底不可逆的摧毁之前硬盘上保存的密钥的话,那么之前的通信内容可以保证无法被解密。

但是在实际部署的过程中可能遇到的问题包括:
密码被复用:除非有自动化的密码配置方法,否则实际使用过程中几乎无法避免复用密码的问题。从协议层面上也不能避免密码的复用。
密码无法被彻底和不可逆的摧毁:一般来说除非是RPMB或者TPM的NV存储,都应该认为保存的任意内容的任意版本可以被恢复。一般的普通文件系统环境和普通的硬盘很难保证内容无法恢复。比较可怕的问题是只要有一个版本的内容泄露,之后的密码就全部可以被推测出来,每个小时都写入一个版本的话迟早会有一个版本藏在哪里没删掉。泄露一个版本之后的通信就直接全军覆没不太好吧。

总体来看就是个低配版本的puncturable encryption。虽然设计上没有什么问题,但是有一些假设在实际环境中并不容易实现。

我想出了一个改进的方法,客户端发送给服务器的连接里面带上一个客户端DH参数,服务器在收到这个消息后就随机生成一个DH参数并保存,然后 新密钥 = hash(旧密钥+DH结果), 然后把这个服务器DH参数返回给客户端。客户端在收到新密钥后就用新密钥建立连接。服务器端在之后收到新连接的时候,如果是用新密钥的连接就销毁旧密钥,然后保存新密钥,如果是旧密钥就重新发送服务器DH参数。

这样的话,首先如果多个客户端都使用一样的密码只要一个客户端连接剩下的客户端就会失去同步连接不上了,自动防止密码公用。然后就算某个以前版本的密钥泄露了,因为不知道中途的DH参数也没办法推断出来未来的连接的加密密钥。

@RPRX
Copy link
Author

RPRX commented Mar 3, 2021

@xiaokangwang

先前我已经提了一个 改协议 来实现前向安全等更高级特性的方案 #177 ,你提到的“改进的方法”与我之前已经提过的 #177 所实现的事情没有本质区别,反而更加复杂。但是当时他们不愿意改协议,所以这里的 #178 是以 不改协议 且同样不引入长期额外信道为前提的,基于此,目前没有发现更好的想法了。所以首先需要记住这些限制,然后说回想法本身:1.每个用户的密码变化规则都不同,且密码被复用的超低概率不会造成问题。2.旧密码未被摧毁的问题确实考虑过且值得关注,一般来说新密码会覆写硬盘上的旧密码,或者至少擦除旧密码,实现上需要参考一些现有的数据安全方案。最后还是重新提一下,这里是种种限制之下的方案,对比时不能忘记这一点。

然而鉴于前几天我又提出了 #183#184 ,改协议或更加依赖 TLS 已不可避免。

@Mygod
Copy link
Contributor

Mygod commented Jun 19, 2021

As per #178 (comment), neither #177 and #178 gets you forward secrecy. Fundamentally, to get forward secrecy, you need key exchange, and key exchange seems to require public-key crypto [Impagliazzo-Rudich, STOC'89], and the key exchange protocols in neither of these proposals are secure when one party is compromised later.

More importantly, Shadowsocks does not guarantee forward secrecy, and this could be easily mitigated by adding a TLS plugin.

@RPRX
Copy link
Author

RPRX commented Jun 20, 2021

@Mygod

有趣,我觉得你完全无法理解我设计的这两个机制的精妙之处。

#178 在保持 0-RTT、不引入额外长期信道、不改 Shadowsocks / VMess 类通信协议结构的前提下,实现了当前存储的密钥泄漏并不会导致以前的绝大多数流量被解密,这是现在的静态 PSK 所无法做到的。 此外,对于 SS,这个机制还可以彻底识别长期重放攻击。

#177 在保持 0-RTT、不引入额外长期信道的前提下,通过精心设计的通信协议结构、密钥下发机制,相较于 Shadowsocks 实现了:

  1. 当前存储的密钥泄漏并不会导致以前的绝大多数流量被解密。
  2. 即使当前存储的密钥泄漏了,以后的流量也不一定能解密。
  3. 彻底识别长期重放攻击。
  4. 防止一种极具破坏性的攻击,@DuckSoft 尚未将它完全公布,所以我还是暂时不能说。
  5. 自动限制设备数量。

另一类方案是引入额外长期 TLS 机制来定期更新密钥,但无法实现 4 和 5(尤其是 4),而且都上 TLS 了为什么不直接用 TLS?TLS plugin 不是不可以,只是现在跑在 TLS 上的协议已经很多了,不缺 SS 这一个(且它没有 UoT),我还设计了性能 MAX 的 XTLS,它还会继续进化。另外 TLS 的缺点是暴露的信息多,所以我在这里就是设计非 TLS 上的协议,并且裸跑更符合 SS 原本/常规的用途。

@xiaokangwang
Copy link

xiaokangwang commented Jun 21, 2021

I would like to thank @RPRX for notifying me to know about my incorrect understanding of words.

I have removed a post I made previously about this topic. This scheme achieves forward security(to a certain extent) by making sure that future attacker will not be able to decrypt the traffic in previous sessions since the key has already been updated. This mechanic is similar to Rekey(11.3.) in Noise.

I would also like to apologize to @RPRX for this.

@rurirei
Copy link

rurirei commented May 7, 2023

sorry that i'm started learning on the protocol or security base.

https://shadowsocks.org/guide/aead.html
HKDF_SHA1 is a function that takes a secret key, a non-secret salt, an info string, and produces a subkey that is cryptographically strong even if the input secret key is weak.

is iv in the request not encrypted as there no forward-secrecy? and what intended to make some subkey here as even this not guaranteed a security, related maybe #178 (comment)?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

10 participants