1
$\begingroup$

I'm now trying to design a more secure key-change algorithm to replace widely used DH.

However, I am only able to prove that my algorithm is more secure logically, which means I can only prove it from a reasoning rather than mathematical perspective.

Thus I wonder if there is a standardized procedure that I can use to evaluate my work.

If unfortunately there isn't, is it ok I just collect every existing attacks on DH and try to use those method to attack my own method? Is it a reasonable way to prove my algorithm secure?

$\endgroup$

2 Answers 2

1
$\begingroup$

No, if your system is really different about DH-key exchange, it's not really relevant to notice that attack designed specially against Diffie-Hellman protocol are not efficient against yours.

There is three ways to compare your protocol to the another one:

  • First, it would be good to prove by writing a security proof that your protocol is at least as secure of some know algorithmic problem. And if the problem is known harder than the Diffie-Hellman problem, it could be interesting. BUT you have to notice the Diffie-Hellman (decisional or computational) problem is a parametrized problem. And the hardness of these problems depends strongly of the choice of the parameter (called the security parameter and with name $\lambda$ in research papers). So if you want to be honest you have to choose relevantly the parameter to compare both problems (for example you can compare with parameters such that the efficiency of both protocols are the same).

  • Other possibility, you claim that your protocol verify some stronger property than DH-key exchange. Then it would be good to argue your claim with a security proof and also show DH-KE doesn't verify this property (by exhibiting an attack for example).

  • If there is no security proof (for standard property and stronger one). You have the possibility to publicly present your protocol in an academic conference, and let the possibility to researcher to find attacks in your protocol. And then maybe, if with a lot of visibility during years, your claim of security has not been broken, people will consider your protocol secure and will compare the best attack known between the two protocols to choose which is the most secure one.

$\endgroup$
1
$\begingroup$

levgeni gave a pretty good answer; there are a few points I thought I could add:

I'm now trying to design a more secure key-change algorithm to replace widely used DH.

First off, it is quite likely that your new "key-exchange algorithm" is weak. I don't say that only to be mean [1], but also based on the history of proposed cryptographical algorithms (including key exchange) - most of them have turned out to be weak, and this is especially true of designs made by cryptographical novices. And, even when an experienced cryptographer proposes a new system, they will never claim it to be secure [2] - we always say that it needs vetting.

The other issue is that we're about to replace (or supplement) DH (and ECDH) anyways. The reason for this is because of the upcoming threat of Cryptographically Relevant Quantum Computers - if someone were able to build one, then they could break DH and ECDH. And, while we don't believe anyone has one now, they might in 10 or 20 years - and once someone has one, they could go back and start breaking recorded sessions (which would include the DH/ECDH exchange) - hence, we're working on this problem now.

So, unless your algorithm is Quantum Resistant, that is, cannot be broken even with an attacker with a Quantum Computer, well, it's unlikely that anyone would pay attention to it, even if you could show that it is secure against adversaries with only conventional computers. And, one way to see that an algorithm is not Quantum Resistant" is to consider an adversary with a Magic Box that can factor and compute discrete logs - if such an adversary can break your system, then you're not Quantum Resistant. Of course, it doesn't go the other way around - just because your algorithm is immune to factoring and computing discrete logs attacks doesn't mean it is Quantum Resistant - Quantum Computers can do other things too.

However, I am only able to prove that my algorithm is more secure logically, which means I can only prove it from a reasoning rather than mathematical perspective.

What you mean is that you have a plausibility argument that your algorithm is secure. A plausibility argument is better than nothing; however it is not a great deal better. A mathematical proof is what is expected...

Thus I wonder if there is a standardized procedure that I can use to evaluate my work.

As levgeni stated, the standard way is to identify the 'hard problem' (or possibly several hard problems), and then generate a proof that if you can break your key exchange [3], then he can solve the hard problem [4]. Once you've done that, you can try to evaluate how hard your 'hard problem' is (and whether it is harder than the hard problem that DH is based on, which would be either the CDH or the DDH problem).

Unless you've done that, it's be extremely hard to get anyone to take your work seriously.

Of course, even if you've done that (and yes, that's a lot of work), it'll still be an uphill struggle - you still need to get cryptanalysts to look at it. If you have everything written up, you could put it on eprint (and so it'd be out there); you could also submit it to a conference (if it's novel and postquantum, PQC https://pqcrypto.org/conferences.html might be your best bet) - even if the paper isn't accepted, the reviews you get may be enlightening.


[1]: Well, that's not the only reason...

[2]: The one exception would be if he has a proof in hand that the strength of the system can be reduced to an accepted hard problem. However, even in those cases, he is likely to recommend that someone go through the proof thoroughly...

[3]: Ideally, breaking it means "if you can give the attacker the exchanged key shares and a putative 'shared secret', he has an advantage of distinguishing whether that 'shared secret' is the actual value, or a random value drawn from an appropriate random distribution"

[4]: Note the order - breaking your system implies breaking the hard problem. I've seen papers that tried to go in the other direction - "if you can solve this hard problem, you can break my system" - that doesn't actually show anything.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.