Note: Many researchers are justifiably concerned about the fact that Alfred Menezes will be giving an invited talk at Eurocrypt 2012 related to his line of papers criticizing provable security. I share this concern. I hope to blog about his (and Koblitz’s) papers over the next few weeks leading up to the conference.
What follows is something that Yehuda sent me unsolicited.
In an ideal world, people will be gracious and scientists will work primarily to promote science. (I am not naive, and am aware that scientists are people and need to promote themselves. However, self-promotion should go together with the promotion of science and not at its expense.)
The specific issue that I wish to talk about in this context is how to deal with bugs, errors, flaws and so on that you discover in other people’s papers. The right thing to do is to write the authors a nice email, saying that you believe you have found a bug and would like to inform them about it, or be corrected in case it is your mistake. If you are correct, and the authors are also gracious (as they should be), then they will correct their paper and give you a nice acknowledgement thanking you for the correction. You can then continue to do productive research.
Of course, if such a correction requires novel research that you have already done, then the above strategy may not work. In such a case, one can try to be creative in order to be gracious. One such example happened to me when I proved an impossibility result, only to discover that a (contradictory) positive result was published on this exact topic a few years beforehand. I couldn’t work out who was wrong, so I spoke to the authors. After discussion we realized that they were wrong, and that their proof holds in a much weaker model. In my paper, all I wrote was “Our impossibility result does not contradict [X] since their positive result holds for a different, weaker model”. The other authors acknowledged me for finding the bug, and everyone walked away happy. Would I have gained anything by writing “we show that [X] were wrong”; most certainly not!
Unfortunately, not everyone in our community takes this approach. Indeed, there are even people who actively search for errors in order to promote an agenda of attacking the entire crypto-theory community. Two examples are Koblitz and Menezes. You can see their newest paper on eprint. This time they really outdid themselves since there is actually no error. Rather the proof of security is in the non-uniform model, which they appear to not be familiar with. Even after being told about this, they still chose to leave their attack unchanged. You can see my discussion post.
Random bits 
I’m afraid I disagree with Yehuda here.
I agree that, if you think you’ve found a flaw in a published paper, it is a good idea to first send the authors an email and get their reaction. However there is a self-interested reason to do this: sometimes you are wrong and the published paper is actually correct. Thus, contacting the authors is in your own interests and in the interests of good science.
However, I’m not so sure by Yehuda’s suggestion that, if you actually have found a serious flaw in a published paper, you shouldn’t publish it — you should just tell the authors and let them correct their paper as they see fit. I think the research community makes progress by learning from our errors. If we try to conceal those errors, in the interests of collegiality or graciousness, then it feels like we are making it harder to learn from our own mistakes and harder for the field as a whole to improve. Therefore, I worry that Yehuda’s advice may lead to a sub-optimal result for the field.
I do agree that if you find a flaw in someone’s paper you should be gracious about it. But I don’t agree with Yehuda’s statements about what graciousness requires.
I realize no one likes to be told that they are wrong. But look, it’s science. One of the major purposes of science is to increase the chances of learning when we are wrong. We should be fostering a culture which maximizes the chances that we discover we are wrong (when we are actually wrong), a culture that rewards and thanks people who discover we were wrong — not building a culture that tries to insulate us from discovering that we were wrong.
Or, at least, we should be building a culture that makes the whole thing less personal — one that separates criticism of the idea from criticism of the people. It seems to me robust criticism of the idea should always be fair game in any scientific endeavour, and indeed, should be welcomed. That is how we test the strength of our beliefs and ideas.
Well, that’s my take on it, anyway. I don’t know how others feel.
By: CryptoFan on February 28, 2012
at 10:49 pm
I’m not sure that we disagree so much. The question is what sort of flaw you find. If you find a inherent flaw that requires a completely new proof, or you find that a theorem is wrong and actually impossible to achieve, then this is essentially new research and you should certainly publish (graciously). I am referring to bugs in proofs, that may be non-trivial, but can be fixed and the fix does not involve any special enlightenment.
In addition, I am certainly not in favor of concealing errors, and I would like to be rewarded by my finding a bug. However, the reward will be an acknowledgement, and the same treatment from other people. Does science gain from an entire paper pointing out and fixing a bug in a proof (that does not require any brand new ideas)? I think not. Science does gain from the community collaborating and working together to get things right.
By: Yehuda Lindell on February 29, 2012
at 2:00 am
Sorry for over-posting here, but I wanted to make one more clarification. I am VERY against concealing errors. In fact, if an error is found in a paper, then I strongly advocate putting a footnote on the FRONT PAGE of the corrected version so that those who saw a conference version (for example) will know that there was a bug. I am aware that not everyone does this, but then again, we are talking about ideal worlds.
By: Yehuda Lindell on February 29, 2012
at 4:20 am
Let Menezes’ talk stand or fall on its own merits. Why should only proponents of “provable security” be giving plenaries? No harm in a little conflict of ideas, is there? If the crypto community is not mature enough to handle this, given that the tradition of open Crypto conferences is now approximately 30 years old, we should be really worried. PS: I don’t know the technicalities enough to form a strong scientific opinion for either of the two sides.
By: kodlu on February 29, 2012
at 5:46 am
1. It is nice to always confirm the flaws with the authors, but what we are talking about is science but not people, as CryptoFan said. The papers should be published based on contributions and nobilities but not which circles of people which you belong to (which I think there already exist some).
2. Why should we limit our minds to the uniform models? We need something useful and secure in practice, but not something only provable secure in uniform models.
3. Did Lindell really confirm with Koblitz and Menezes whether they already contacted Bellare about the new proof before putting it online?
Generally, I think Lindell is overreacting. Koblitz and Menezes didn’t say HMAC was wrong, but just gave a proof for broader cases. This should be something our crypto community and security industry are happy to hear.
By: Anonymous on February 29, 2012
at 10:36 am
I don’t want to speak for the author(s) here, however my understanding is that they have contacted Koblitz and Menezes in an attempt to correct their misunderstandings, and were not satisfied with their response.
(Also, in this case there was no mistake in the original proof at all! Rather, it was a misunderstanding of the security model being used.)
I won’t comment further about this point, but if any of the parties involved are reading this blog they are welcome to give further details.
By: jonkatz on February 29, 2012
at 10:44 am
Why should only proponents of “provable security” be giving plenaries? No harm in a little conflict of ideas, is there? If the crypto community is not mature enough to handle this, given that the tradition of open Crypto conferences is now approximately 30 years old, we should be really worried.
Let’s be serious, no one is saying that only proponents of provable security should be giving plenaries. If people have an objection about the Eurocrypt talk it is because it will be discussing ideas that are: (a) apparently wrong (in the case of the latest paper); (b) obvious to anyone who works on crypto (e.g., the possibilities of bugs in proofs, attacks outside models, concrete vs asymptotic analysis etc…). In addition to this, the way these ideas are conveyed is aggressive, disrespectful, unproductive and frankly just immature.
No one is saying that people shouldn’t have conflicting ideas. But compare the tone and style of the Koblitz and Menezes papers to, for example, Rogaway’s papers here and here. The latter are much more mature than the KM papers and Rogaway still manages to make his points.
I think the underlying message of Yehuda’s post is: do we want to improve our scientific output while remaining mature and respectful of each other; or do we want to do it by being immature, snide, aggressive and disrespectful?
By: Asterix on February 29, 2012
at 1:43 pm
As another example of a respectful way of publishing conflicting ideas see Goldreich’s essays on trends in the TCS community, on intellectual values and on competition: here.
These essays generated quite some controversy and many people disagreed but they were not personal and immature.
By: Asterix on February 29, 2012
at 1:48 pm
Anonymous, did you look at the KM paper regarding HMAC? You say that they didn’t say that it’s wrong. Well, I quote: “Third, we describe a fundamental flaw in Bellare’s 2006 security proof for HMAC, and show that with the flaw removed the proof gives a security guarantee that is of little value in practice.”; this is from the abstract. They use the words flaw, misuse and more many times in the paper.
And this exactly proves my point. What would our response have been had KM published a paper with the following claim to fame: “We present a new analysis of HMAC, which also gives a uniform reduction. This improves on the previous analysis by BK which is in the non-uniform model.” Technically, it’s the same. However, KM go on a tirade in their conclusions that the proofs are anyway not worth anything and that our research culture leads to many proofs being majorly flawed. Yes, errors are a problem. Yes, things can be improved. No, there is NO FLAW here whatsoever. Yes, KM certainly did say that the HMAC proof is wrong (fundamentally flawed is the term). So, am I overreacting?
And in answer to kodlu: the problem is that Menezes is likely to misrepresent issues and mislead the community, while attacking a large portion of the community. This will not be productive for anyone. We already have enough “theory-practice tension” and this won’t help. In contrast, I would be very happy to hear a panel that openly discusses such issues, with speakers who are respectful and raise the real issues and concerns.
By: Yehuda Lindell on March 1, 2012
at 2:42 am
@Lindell
Sorry, I meant — they didn’t say HMAC was flawed, and what they said is the original PROOF didn’t apply to non-uniform cases.
I’m not sure whether their new proofs are solid or not, but from my point of view, your attitude in the IACR discussion forum and the above article is much more personal (and maybe immature) than KM’s. They are talking the issue in a paper. If you found their paper was wrong, you can simply point it out and everybody will reconsider it. You shouldn’t highlight it as some personal issues. If we consider always being nice and not hurting others’ feelings, it is ineffective, not effective, and it is politics, not science.
By: Anonymous on March 1, 2012
at 3:24 am
Anonymous: just to clarify, and not leave confusing information in the discussion. What you now write is the (correct) summary of what KM should have said instead, but by far not what written in their paper on HMAC. KM do not even mention uniform and non-uniform models. They instead just say that Bellare’s proof is flawed, and claim a “correct” proof.
Either they (implicitly) make the point that any non-uniform reduction in cryptography is “flawed”, or there is a very basic misunderstanding on their part.
By: NonUniformAdversary on March 1, 2012
at 1:43 pm
Relatedly, I ran into a case lately in a different subject where people are publishing papers whose only point is to argue about who should get the credit for discovering bugs in someone else’s paper: http://dx.doi.org/10.1007/s00453-011-9508-3
Make of it what you will, but I don’t think that kind of situation leaves anyone looking good.
By: D. Eppstein on March 1, 2012
at 5:28 pm
One wonders why anyone would think Menezes and Koblitz don’t know what the non-uniform model is. It is quite obvious that they know what it is, but they’re claiming that results in the non-uniform model may not be very useful. Given Rogaway’s 2006 Vietcrypt paper, it’s hard to argue with that.
Somehow it seems that people are very angry with Koblitz and Menezes, and I really don’t understand why people bother.
By: Kristian Gjøsteen on March 2, 2012
at 9:10 am
but they’re claiming that results in the non-uniform model may not be very useful.
We can quibble about style, paper title and manners all we want (and perhaps with good reason), but yes at the end of the day, that is the main claim and it is quite well supported by the facts: the proof in the original paper is correct, but the claim of security in practice is wrong as it assumes too strong a model.
By: Uniform on March 2, 2012
at 2:56 pm
@Kristian: Without Yehuda and this discussion, I doubt most readers of this blog would have realized that KM are addressing the non-uniformity of Bellare’s reduction. I may be wrong, but it seems some people here are taking Yehuda’s interpretation of the technical results in KM’s paper as the actual contents of that paper, and using this to defend KM’s work, without having read their paper in the first place.
There is sufficient evidence to support the claim that they may be unaware of non-uniformity. Indeed, if their goal is to make a valid and (justified!) critique to non-uniform reductions, then why hide it in a paper attacking one specific proof for HMAC, call it “flawed”, and never mention the non-uniform model in the whole paper? And why attribute the “flaw” to the use of rigorous, “tedious”, and “turgid” proof methodologies? And most importantly, why not cite and critique the zillions of other papers using non-uniform reductions, some of them being breakthroughs in cryptography and complexity theory?
It is fairly certain that a paper titled “Another look at non-uniform reductions”, if written properly by the same authors, would have not triggered widespread outrage as this one did, and may have contained very interesting insights.
By: NonUniformAdversary on March 2, 2012
at 3:19 pm
Rumor has it that KM got one-upped by another cryptographer a while ago. The reason KM were beaten that time was because their proposed scheme was not provably secure, and the cryptographer fixed this by making an epsilon modification of the KM scheme. He got all the credit (there was money involved) while KM didn’t get nothing. Since then KM have been pissed off at “provable” security.
I don’t know if the above is true (is it??)… and even if it is I find it hard to believe that KM haven’t gotten over that incident yet.
#politics_vs_science
By: wasting my time on March 2, 2012
at 4:42 pm
@wasting_my_time: Spreading such an unsubstantiated rumor here is not productive.
By: mikero on March 2, 2012
at 11:53 pm
It seems to me that Koblitz and Menezes deliberately try to avoid technical words, and instead try to describe what is actually happening. This is a laudable goal. Which explains why they don’t use technical words like “non-uniform”. (Coincidentally, a casual reader of Bellare’s paper might not appreciate the exact meaning of “exists” in the theorems.)
One must also remember the two purposes of proofs if cryptography. The first is to understand _why_ the scheme is secure. The second is to provide solid evidence _that_ the scheme is secure. Achieving the second purpose tends to result in tedious and “turgid” proofs, because you really have to dot every i.
I see no reason why we shouldn’t do both though (even if I am not very good at it myself). But I claim that providing solid evidence for security is really important for schemes that will be deployed, such as HMAC. In my experience writing proofs, hand-waving “why”-focused security arguments too often overlook stuff.
By: Kristian Gjøsteen on March 3, 2012
at 5:09 am
1. On the issue of whether it is within the norm for cryptologists to apply the word “flaw” to others’ work, the following paper [C2]
Click to access 24420093.pdf
suggests it is, since the title “Flaws …” was approved by the Crypto 2002 committee.
2. On graciousness: I don’t remember being contacted about [C2] (though I commonly forget much [*F]), before or after, or even [C2] arising in subsequent conversation with some of the [C2] authors [*F]. I do disagree with the points in [C2], perhaps I am biased, and was at first, naturally, a little annoyed with the tone (i.e. “Flaw”), but not enough to request a title change [*F]. Just to be clear, I don’t now take any issue the tone in [C2], so I’m raising it just to make the point that such tones (and levels of graciousness) may be the norm, and that perhaps we should try to be thicker-skinned. Maybe I’m naive, but in the long run it is the point (and clarity thereof) not the tone that matters, at least to me. To clarify: tone and clarity are orthogonal, in the sense I mean. E.g. the KM papers adopt a provocative tone in an effort to, they claim (among other things) to have greater clarity in provable security papers.
3. Finally, since I’ve so far been too lazy to read the Bellare or KM papers in detail, and since HMAC is so widely used, and since I may need to know in the future what MAC to recommend to implementers: I’d really relish a clear summary paragraph of the HMAC (provable) security status, after the issues have settled (if they haven’t already). E.g. does the updated KM paper now give a good summary?
By: Dan Brown on March 6, 2012
at 12:42 pm
the KM papers adopt a provocative tone in an effort to, they claim (among other things) to have greater clarity in provable security papers.
I’m sorry but could you expand on this argument about clarity in provable security papers? I’ve read many math papers and they were some of the most opaque papers I’ve ever seen (even more so than physics or biology).
Research papers tend to be written for other researchers, i.e., experts in the area. So a lot of the basics are omitted. This is done for at least two reasons: to fit the paper within the page limit; and to make it less boring to the reviewers. This happens in all scientific fields and math is probably the worst culprit in this regard. So I don’t quite understand why KM make this into such a big issue in the case of cryptography.
It’s a little bit like a cryptographer complaining that research papers on topology are too dense and hard to read. Of course they are! They are written for people who understand topology. If you want to learn provable security (including, e.g., the non-uniform model of computation) you shouldn’t expect to learn it from research papers. You should go buy a book, read lecture notes or take a class.
By: Anonymous on March 6, 2012
at 1:28 pm
Well, KM are not the only people in crypto who tend to cause allergic reaction. I can name a few who stir debates. Some of them know what they are talking about, some of them – do not.
Without entering the specific discussion of whether KM are right or not in their specific criticism of provable security, one should consider their long standing crusade against provable security. ProvSec suffers from several flaws:
1. Provable (under condition X) – too often the conditions are not well described (and sometimes are too well hidden), and in many cases, the ProvSec community assumes that the entire world understands that there is this “under condition X” with all proves, forgetting that most engineers implementing schemes can’t necessarily parse these conditions.
2. Tightness of reductions and meaning of life – way too often the reductions are such that for a practical security level of 80 bits, one needs a protocol that sends over 1 MB of data, or perform too heavy computations (see for example the Fully Homomorphic Encryption in 20 something minutes). While these things do improve our understanding of crypto (and obviously FHE is a great tool with lots of potential), the ProvSec community usually disregards real life, and oversells the contribution (the same is also true for point 1).
3. Small improvements, HUGE headlines – consider Eurocrypt/CRYPTO, the top-notch crypto conferences. A 15% reduction in circuit size – not interesting enough. A 20% reduction in running time of a real life cipher – out of scope. 50% improvement in finding collisions – usually rejected (unless the most important ciphers). To be compared with the ECC community where a 6% reduction in running time is Eurocrypt-worthy, and the ProvSec community where small changes (seriously, we are talking about small changes) to the security model, or the efficiency of the protocol (e.g., 1% for 80-bit security level) – Greatest result ever.
4. Complete contempt towards other crypto feild – this does not describe all the ProvSec community, but there are several ProvSec community members who keep on complaining about practitioners who refuse to adopt their constructions which are provably secure and rather use ad-hoc solutions (e.g., SSL, AES, SHA-3) which are not provably secure (they are secure, just not provably secure). For example, open Oded’s book about foundations of crypto (or think of Oded saying that there is only one type of security – the one that he can prove). Without entering into whether a x10 efficiency lose is where I would suggest to adopt a provable security solution (or a x2 or no performance lose), some ProvSec people feel utter contempt towards those who actually do the cryptanalysis (symmetric key, LLL, BKZ, etc.). Even though I have to admit that usually it’s the symmetric key cryptanalysis/hardware torturers who receive the short straw. The public key cryptanalysis people can speak about asymptotic behaviour (while AES attacks always require at most O(1) work, it’s just the huge constant that keeps annoying people).
The best example to 4 is the recent Eurocrypt paper by Standaert showing what leakage is in real life. Did it bother the ProvSec community to change their model? not a bit. Seems like “hey, we developed this model, let’s see what we can do with it”, which is interesting, but then why is there is always the text about how this model has something to do with real life? You want to have a theoretical question – be my guest. We do learn from these things, but then why do you keep on overselling the relation to real life?
Now, all of these points are certainly not a reason to personally attack no one, and KM can certainly be insulting, but so does many ProvSec champions, and I’ve never seen the ProvSec community go to fight the battle of “behave nicely” before they got burnt (not that there is no need to try and make sure crypto is friendly towards “competition” and people with other views).
By: kilmo on March 12, 2012
at 10:12 am
kilmo: I actually find that the reverse is the case. I hear more practitioners (I will assume that you consider yourself in this community) belittling the contribution of theory than the contrary. I also don’t think that Oded’s book is any example. Oded is a theoretician; he researches theory only. His book is a book about theory. He makes no claim to doing practical cryptography. He believes that a strong foundation in theory helps practice, but he is not doing practical cryptography and is also not belittling it.
I also am a strong believer that a strong foundation in theory helps practice. However, I have no contempt whatsoever of cryptanalysis or practice. By the way, from my experience in Crypto and Eurocrypt committees, papers on cryptanalysis get rejected by cryptanalysis people and certainly NOT by theory people (who have no opinion on it).
Regarding open contempt: I have never ever seen a paper or heard a talk by a theoretician who shows open contempt of practice and criticises an entire field, like [KM]. (Now, I am sure that there are some theoreticians with such contempt. However, they are not writing papers about this contempt and are not given wide support for their contempt.)
One last word: I DO believe that there is merit to some claims made by [KM]. Indeed, proofs need to be checked more. Indeed, a discussion on the usefulness of theoretical models in practice is important. And more. However, a discussion based on mutual respect of both sides is much more constructive and productive than a mud-slinging match.
By: Yehuda Lindell on March 13, 2012
at 3:17 am
Dan Bernstein gave a rump session talk on this subject at FSE 2012. Here is a link to the slides:
Click to access slides.pdf
By: Anonymous on March 21, 2012
at 2:03 pm
Thanks for sharing Dan Bernstein’s rump session talk! That was informative. It has me thinking there may be something to the criticisms. For those of us who are not fully up on the details of the controversy, can the folks who are objecting to Koblitz and Menezes respond substantively to the criticism explained in Bernstein’s rump session talk?
P.S. Make sure you are familiar with time-space tradeoff and precomputation attacks before reading Bernstein’s slides; otherwise some aspects may be inscrutable (e.g., where 2^85 comes from).
By: CryptoFan on April 3, 2012
at 4:49 pm
Actually, I think Bernstein has a valid point (that was not articulated, at least not explicitly, in the original Koblitz-Menezes paper).
By: jonkatz on April 3, 2012
at 5:26 pm
Apparently, the controversy has reached FakeIACR twitter account (22 March – https://twitter.com/#!/FakeIACR)
By: FakeBartPreneel on April 4, 2012
at 10:35 am
This discussion (and Yehuda’s comment at http://eprint.iacr.org/forum/read.php?12,604) tend to show up in search engines, so it seems warranted to add additional pointers:
Koblitz and Menezes have responded to the discussion, both by posting an updated version of their HMAC paper (http://eprint.iacr.org/2012/074) and by posting a new paper “Another look at non-uniformity” — see http://www.anotherlook.ca/nonunif.shtml for links to that paper and to additional material (such as slides at http://cacr.uwaterloo.ca/~ajmeneze/anotherlook/ECC2012.pdf, for the impatient reader).
Regarding the question of whether or not there is a “flaw”, here is the core of an essential quote from the latest version of “Another look at HMAC”:
“The claim that Bellare’s proofs are in the non-uniform model of complexity may be puzzling to readers, since the paragraph titled “Techniques” in the Introduction would lead those who understand the uniform vs. non-uniform distinction to conclude that Bellare is not using the non-uniform model of complexity. He writes: “[…]” […] this statement makes no sense if proofs are valid only in the non-uniform model. Thus, a careful reader would be led to believe that Bellare’s results are intended to be valid in the uniform model of complexity.
Moreover, in the next section we show that the analysis of his theorem that Bellare provides in §3.2 of [1] is flawed, because it implicitly assumes that his proof is valid in the uniform model of complexity.”
(I do realize that this update continues to side-track the actual subject of this blog article, which is _how_ to deal with flaws. In this regard, it seems fair to say that Yehuda has observed a flaw in Neal Koblitz. Do I agree with how he has reported it? Well, if I didn’t, I probably shouldn’t tell you here.)
By: Bodo Möller on November 30, 2012
at 5:01 am
[…] Although the absolute confidence we can have in this argument is the subject of debate and some controversy, it is still very reassuring to me about the security of HMAC, and I am not […]
By: Is SHA1 secure with such many inputs Z that Z = constant secret X variable public Y? | CL-UAT on December 29, 2014
at 10:34 am
[…] by Koblitz and Menezes six years later. The Koblitz–Menezes observation was at first met with denials, but my impression is that the denials stopped after my followup paper with Lange, […]
By: cr.yp.to: 2017.07.23: Fast-key-erasure random-number generators | Artificia Intelligence on July 24, 2017
at 9:49 am