A Linear Annihilator Property and Strong Biases with Original DES S-boxes

In 2004 I have published a paper [Crypto 2004, Santa Barbara] in which I explain the concept of the so called Bi-Linear attack on DES. The old attack was not extremely strong. It is possible to see that two conditions would be necessary for such an attack to somewhat work well in cryptanalysis of DES:

  1. There must a strong connection inside the P-box so that a pair of bits goes from one S-box to another and back. Unhappily there are extremely few such cases in DES, for example the pair 3,17, and the attack is prevented by a strong P-box.
  2. The P-box must have super strong LINEAR annihilators such as for example two Boolean functions inside DES would have to satisfy a condition like:

Z*(a+d)=0

Needless to say they don’t, and this attack is just unthinkable (a detailed description of one attack of this type can be found in section 11.2 of this paper). There are extremely few cases where point 1. would work and in fact the situation is far worse for point 2.. It is possible to see that the probability that Z*(a+d)=0 for a random Boolean function is

(2^-9.5)^2.

3. Moreover it is easy to show mathematically that such a Boolean function cannot be non-linear and balanced at the same time [a little theorem which we leave as an exercise for a reader, solution will be published soon].

So we have an extremely weak attack on DES which does not and cannot work due to points 1. 2. and 3. However:

Reality is More Interesting than Fiction

The idea is that we need to relax this attack a little bit and eventually the obstacles 1. 2. 3. can be removed or circumvented.

It will come as a shock to anyone who has ever studied DES but linear annihilators DO EXIST for the original DES S-boxes. For example we have these two examples:

(1+R14+R16)*(W4+X4+Y4+Z4+1+R12+R14) = 0

(1+R16+R17+R20)*(W5+X5+Y5+Z5+1+R17) = 0

Specialists of Boolean functions would say that “some output linear combinations of DES S-boxes are 1-weakly-normal” see this paper. This is actually a very strong property. Extremely few Boolean functions have this property (actually also about 2^-9.5 of all Boolean functions on 6 variables).

 

New Attacks

So obstacles 2. and 3. are removed. Where do we get from there?
The question really is how to remove obstacle 1. as we are NOT allowed to change the wiring of DES in order to make the job easier for us. The answer is that we need an attack able to exploit properties such as above. The existence of such an attack has been an open problem since 1985, the famous mystery paper by Adi Shamir. We are going to publish such an attack in 2019.

More Observations

For now, let us look at the underlying DES facts.

Why is our property related to the one observed by Shamir? Shamir observes that for many DES S-boxes the sum of 4 outputs such as (W1+X1+Y1+Z1) for the 1-st S-box is trongly biased. If so either (W1+X1+Y1+Z1) or (1+W1+X1+Y1+Z1) will have a large number of annihilators (it is easy to see that the number of annihilators depends on the Hamming weight or the number of 1’s in the truth table of a Boolean function and nothing else, see Thm C.2. in Appendix of this paper.) Then we will not be surprised to see that for example:

R01*(R04+1)*(W1+X1+Y1+Z1)=0

Now our new properties are yet stronger, we have only one affine factor:

(1+R16+R17+R20)*(W5+X5+Y5+Z5+1+R17) = 0

Moreover the connection between the size of annihilator space and the biases works both ways. We have also accidentally discovered that not only sums of 4 outputs but also things such as

(W5+X5+Y5+Z5+1+R17) 

are strongly biased with the actual original DES S-boxes.

This is new, and was not observed before and not contained in properties presented by Shamir, or cannot be a consequence of these previously observed properties, as we added an affine function. It extends the properties discovered by Shamir with new correlations not studied before, and more importantly with linear annihilations and their applications in cryptanalysis. An actual attack which exploits this type of properties will be presented at ICISC 2019.

Walsh Spectrum Connection

More generally we observe that a sum of all 4 outputs of some DES S-boxes can have more than one very strong correlation with linear functions. Is there are bigger picture we can see here? Yes, the set of all such correlations have been studied since 1970 [yes! in 1976 was already a routine tool, a proof can be found in slide 33  here] and today it is known under the name of Walsh spectrum. Here are the Walsh spectra for the sum of 4 outputs for the three DES S-boxes studied above:

W1+X1+Y1+Z1 {0: 19, 4: 27, 8: 11, 12: 3, 16: 1, 20: 1, 24: 1, 36: 1}
W4+X4+Y4+Z4 {0: 54, 16: 8, 32: 2}
W5+X5+Y5+Z5 {0: 32, 8: 30, 24: 1, 40: 1}

Extremely bad, yes? Well not quite.
We need to observe that this sort of things happen frequently even for Boolean functions chosen at random. It is clear that from the point of view of diffusion or the P-box, attacks which involve all the 4 outputs of each S-box are going to be the hardest to make, or will involve larger numbers of simultaneously active S-boxes. The fact that it happens here when all the 4 outputs are used and not with say W1+Y1, should possibly be considered as evidence that DES was designed to be particularly strong against our attacks. An attack able to exploit such properties will be presented at ICISC 2019.

 

 

A New Attack on Data Encryption Standard (DES)

There is abundant literature on the security of Data Encryption Standard (DES or 3DES). Today we have released a new way to attack this cipher, see Section 11 in here. Anyone who reads this paper should immediately see that the high confidence which have developed over decades in research community about our ability to design secure block ciphers was never justified in any way and an incredibly rich space of attacks with unique powerful features is now available to study.

 

 

 

 

 

 

Added Jun. 2019: here are slides presented at CECC 2019 (invited talk).
Added Oct. 2019:  here are slides presented at the 2019  Symposium on Cryptologic History, 17-19 October 2019, US.

ZeroCash was broken, and nobody have noticed

A bug which allows unlimited creation of coins was found and fixed in ZeroCash.
It is a sophisticated and subtle security flaw. We read that:

To exploit the counterfeiting vulnerability, an attacker would have needed to possess information found in the large MPC protocol transcript that was made available shortly after the launch of Zcash. This transcript had not been widely downloaded and was removed from public availability immediately upon discovery of the vulnerability to make it more difficult to exploit. The Zcash Company adopted and maintained a cover story that the transcript was missing due to accidental deletion. The transcript was later reconstructed from DVDs collected from the participants of the original ceremony and posted following the Sapling activation. 

Source: ZCash blog here.

Added May 2019:
For decades we have heard toxic propaganda claiming that open source software is secure, that peer-reviewed research is correct and accurate etc. Again evidence says the contrary: In Australia they had printed and circulated 46 million bank notes with a typo and nobody noticed for 6 months.

The Tale of Two Evil Empires

George Soros decided in his old days to pick up a new fight.

Let us be clear about who is George Soros. This man represents simultaneously what is the best and what is possibly the worst, inside our barely democratic Western pseudo-liberal but generally still rather free world (for now).

  1. Wisdom and great intelligence, great sensibility and a noble character, and a great ability act and change the world on his own, some sort of superman for some and for himself. A man who played an important role in the fall of the Soviet Empire.
  2. However he also is one of the most hated men on this planet. He is the usual suspect, accused of all sort of evil actions and subversive activities. He represents in a collective imagination of many people, the dark criminal conspiracy side of the free world.

What is the new fight he is proposing?

It looks like the free market economy and the free world, but also simply the human race, has two new enemies.

  • At the end of 2018 he started to explain that the evil empires of Google Facebook and other Internet Giant businesses need to be at least heavily regulated if not broken or destroyed. I would say that if George Soros makes 10 billion dollars profit on short-selling share of some high tech companies it is OK: probably the planet is going to make 500 billion dollars in profit on getting rid of these monopolist fraudster and tax evading businesses which aim to dominate the global economy through asymmetry of information and exploitation of big data, algorithms against consumers until recently, and now simply robots and artificial intelligence against the human kind.
  • In early 2019 Soros comes back and points at China, as an eminent example of an authoritarian regime which has now evolved, past the market economy stage, into an empire on the verge of dominating the whole planet, due to industrial dominance, and which is also directly competing with our US-based Internet giants for world dominance.

It is a pity that we have recognized this earlier. That our politicians are either imbeciles or they simply work for mafias and lie to us every day. That every day we are victims of fraud which is here not help us but in order to make our lives miserable. That we voluntarily submit to the totalitarian project of the Sillicon Valley, the worst enemy of freedom we have known since fascism and communism have lost in the last century.

Soros proposes that the United States should should “stop waging a trade war with practically the whole world”, and simply “focus on China” and China alone. He proposes to crack down on the Chinese telecom and electronics industry and on their domination inside our connected devices. I think George Soros has (again) picked up a great cause and a great fight. It seems in fact that the prophecy of Ross Anderson from 1998 is coming true: what happens with top-dog country policies when you stop being the top dog: you get hit very hard.

Long live George Soros, whatever are his motivations, nice or not pretty, we need to listen to him and embrace the fight against BOTH evil empires. The emperor has new clothes. We need to say no, try to stop the domination of the world by neither of the two totalitarian organised crime syndicates which emanate from both sides of our planet. We need to stop the construction of a totalitarian dystopian future, when the human race will be enslaved, no longer by financial markets run by Mr. Soros and his friends, but much worse: by a totalitarian dystopian machine economy and mass surveillance capitalism where humans matter very little.

Happy Birthday Bitcoin, 10 Years!

On January 3rd we celebrate 10 years since bitcoin network started operation. Long live all crypto currencies, especially those which actually are real innovators, and bring new technology such as advanced crypto techniques to the market.
Let a thousand crypto flowers bloom.

P.S. It is also 20 years and 2 days after the introduction of Euro.

A Protest Movement at UCL

Spontaneous discrete protest movement of an individual against the mafias which are in charge of cyber-security,  cryptography research and education at large worldwide.

Students asked me what is my protest against and I have responded:

It is against hate. All the hate you receive because you are different and you don’t have the same ideas or just because people don’t like you, for example because you are a geek, or because you are yourself, a semi-autistic pathological (not very social and, working on controversial topics) fiercely independent researcher. Or because you speak a foreign language. Or for no apparent reason.

I wish that our public institutions, governments, universities and also public spaces such as say Internet or bitcoin network, or say the mass media, or say the crypto research community, would be AT LEAST  neutral (if not benevolent). More often the not,  they are rather evil and malicious, work the benefit of for vested interests which sponsor and support them in a variety of ways. A perverse system meant to do harm to our societies. Each time organizations achieve strong dominant positions, we should immediately stop trusting them. We need to fight for a more decentralized economy. We have an excessive concentration of power and money in the hands of too few individuals.

An example is how scientific research is manged in most countries:  gangster science, the primary substance of which is “clerical power” (a bit like in Iran) by people who by definition are always right and other are by definition always wrong. We have for decades indulged in fat cat science policies which benefit only some top individuals and which make the lives of other miserable. Scientific research is a rat race in a proper sense: bad behavior and aggression against fellow scientists is encouraged.  Too much so called competition, which is frequently fake, just doing harm to each other; too little cooperation, too much of science with powerful sponsors and strong incentives to lie and cheat etc. The results of this are primarily bad research and bad education. Sponsored education meant to mislead and brainwash the public and also the industry and the government circles. When I started doing research in cryptography in the 1990s most researchers were I think honest and candid (though extremely naive!). I believe this has changed irreversibly and today you cannot survive in research you don’t submit to the dominant corrupt and sectarian ideology and ideas, and also when you even sometimes just say what you think. Research should produce knowledge and create jobs for sure, but also enlighten and educate our societies. I must say we don’t do it well, or not well enough.

Remark: When half of UCL was on strike I did not participate. I am a perfect non-conformist known for having very strange ideas. Expressing your point of view is not illegal or not yet.

 

 

How to Backdoor a Block Cipher

I have written an elementary tutorial and a first proof of concept
about how to backdoor a block cipher in a quite general setting.
Potentially it applies to any block cipher.
Success is not guaranteed though, see the paper.

ADDED 2 JAN 2019:
a new paper shows that invariants of higher degree are substantially more powerful. Instead of a progression, we have a qualitative leap in what can be now achieved: see new paper.

ADDED 4 April 2019: here are slides presented at WCC 2019.

ADDED 18 October 2019. Here are slides presented at NSA Crypto History Conference on 18 Oct 2019.

The Low Cost of 51% Attacks

A web page shows that many crypto currencies lack protection against 51% attacks. For example to double spend in Dash, one needs to pay only 14K$ per hour. To double spend in bitcoin private, 1000$ will suffice. And course benefits of double spending can easily outweigh the costs.

In addition some of the higher numbers are questionable. There is almost certainly an easier way to command 51% of bitcoin hash rate for one hour than paying 650K$. It is sufficient to hack some pool servers, or directly the software run by miners. Luckily for bitcoin, there exist vaste privately-owned mining farms where the software and the hardware are also proprietary.

ADDED: This is how Bitcoin Gold has lost all credibility.

ADDED LATER: And this is how ETC has lost credibility also.

Who Can Stand Up Against Abusive Internet Giants? And the Original Sin of the Internet

These companies (Facebook, Google, etc) known as Internet Giants violate our privacy everyday and they have corrupted our minds and our economy worldwide. They have built a totalitarian dystopian future which is here already, where humans and business alike are enslaved by a digital mafia which aims at controlling and taxing the whole global economy through mass surveillance and stalker economy. Our consent is fake and forced, we actually click on 50 Yes I Agree pop-ups or security alerts daily without ever reading them. We buy a device and instead of owning it, it owns us. We let it do what it likes, like recording our private conversations 24/7, our emails, our clicks, etc, and in order to sell these “data” to other companies, and to use it against our will, against our values and against our laws. In the modern economy, companies spend increasingly large amounts of money in an effort to acquire a customer; and once they have him, captive, they treat him like a piece of shit. When we contribute to the digital economy we contribute for free through open source software and our YouTube videos and tutorials. We are not customers, we are not individuals, we are now rather slaves (or sheep, or pigs maybe).

The Internet Giants has transformed the human race into obedient apathetic animals which are easily manipulated and which work for the benefit of some clever yet abusive corporations (or totalitarian regimes). And there is only one guy worldwide – Max Schrems – who dares to fight Facebook and Google in courts for violating the laws. And another one who is trying to educate us about cybersecurity. And also few more. And that’s it.

An interesting historical insight about WHY we have all this, is the sort of original sin question, also more recently  explained here: “When the internet was built, free and open, it meant that advertising was the only obvious way to make money and that turned into surveillance.”

Another question is, if Google and Facebook do all the mass surveillance at a global scale, what is now the job to do for the GCHQ,NSA etc? Many experts say that police forces are by far more helpful defending us against terrorists than modern cyberspace intelligence capabilities. Max Schrems is also defending us against some ‘particularly large terrorists’ :-). But again, if Google knows everything, now a country in order to get all the intelligence they will ever need, should just blackmail the Internet Giants for access to the data. The answer is probably that these agencies in modern time are NOT that much about intelligence gathering. They are about staying ahead of the game. They are here to develop even more sophisticated technology for, well, what? Either future cyber-crime to be committed. Or to improve defensive security engineering in order to defend us against future crimes. This ambiguity is here to stay.