What is the Purpose of REF?

Today, Jo Grady, general secretary of my university trade Union (UCU) wrote these words to all academic staff who are members of the union:

“we are asking you to withdraw, where possible,

from activities relating to the REF […] […]  

These activities are important to employers but they damage our sector.

They rely on inappropriate metrics of quality; that create

perverse incentives and prevent us from doing the front line

teaching, research and professional services work that really matters.

Exercises like the REF tend to increase our workloads,

waste money that could be invested in staff, and exacerbate

our anxiety and insecurity by subjecting us to unfair,

unhelpful performance management procedures. “

No comments.

30 Years Ago

Exactly 30 years ago, Stasi was dissolved. 13 January 1990. 91,000 full time employees and 189,000 unofficial collaborators and informants lost their jobs and privileges.

The German government has done a lot to preserve anything which Stasi has ever done. Some links:

  • At this moment in Brussels, inside the EU Parliament there is an exposition on this topic.
  • Here is a paper about Stasi from 2017 published in Wired.
  • Putin had close ties with Stasi.
  • Here is some art work about a Stasi prison by Karolina Spolniewski.
  • And here is a video interview by Bernd Lippmann, a teacher who was thrown into a prison at one time and one of some 34,000 political prisoners, later evicted, and for whom a huge amount of money (a ransom) was paid by West Germany, in order to free these prisoners.
  • And here is a paper on cryptography developed by Stasi and used to protect all sort of communications for the German government during the Cold War.

Remark added later: 13 January 2020 was the first case of Coronavirus outside of China. An old lady from Wuhan… Conspiracy theories will thrive!

A New Documentary about WW2 Cryptanalysis of Enigma

A new documentary tells the story of the discovery of one of the most important cryptography papers of all times. We are talking about an extensive technical report written in German language and entitled “Kurzgefasste Darstellung der Auflösungsmethoden”. For some 80 years it has remained classified, part of the so called Gustave Bertrand WW2 archives.

It was written presumably in France, in early second half of 1940, by Marian Rejewski and Henryk Zygalski, though the author names are in fact, not at all specified(!). It seems also that Alan Turing, Dilly Knox and other UK authors were also involved in producing this report. This is, because, instead of a list of authors, this report is written as a summary, or a survey, and very much like a manual, summarizing what was known to the whole group of people. It contains in fact a very clearly marked  list of named contributions, many of which are made by UK cryptologists. For example all Jeffreys, Herivel and Knox are named inside as contributors, see Fig. 1 here. If the authors are not specified, and in absence of further factual discoveries, this report could also be considered as joint work contributed, directly or indirectly, by all people named inside(!).

It is a concise and very detailed summary of all known attacks on Enigma as of 1940. A monumental document which shows how cryptography and cryptanalysis have developed in 1930-1940, with a summary of presumably everything which was known to the allies [Poland,France and Britain] about breaking Enigma codes, at the time.

In fact not quite so or not yet. The title “Kurzgefasste…” suggests that a longer even more detailed document may have existed, which question is also discussed inside this documentary. In fact we know for sure, that some additional cryptographic and signals intelligence knowledge and expertise, and numerous additional concrete decrypts of WW2 messages, have existed at the time, and were known only to yet fewer people. It is believed that these things were however shared with Bletchley park, or/and countries more directly concerned such as Switzerland, more on the need-to-know more ad-hoc basis. It was estimated [as reported by Jean Medrala who has spent a lot of time studying French military archives] that about 50% of decrypts done by Polish code breakers working on the French soil were dissimulated, and not communicated to Bertrand, for some time, and at least until the late 1970s, when Bertrand has written his memoirs. In particular we should consider that knowledge and expertise concerning the decryption of Russian messages was considered as even more sensitive than anything concerning Enigma. It was known to a yet smaller circle of people and almost certainly this part was also not known at Bletchley Park either, and was shared with the UK on a different basis. Private correspondence of WW2 code breakers, preserved by their surviving family members, suggests that they did not in general trust Bertrand, who officially worked for the Vichy government(!). We expect that additional facts will brought to light, and will be published in the near future.

Observation: We should note that the method of Sillies, described by Welchman in The Hut Six Story, will be the first one, not known or not shared with the Polish and French side. This even though very clearly the report shows how the attack method of Herivel, from exactly the same period became operational, with contributions made on both sides of the Channel. These methods were operational in second half of 1940, after France was overrun, and was based very clearly on observations and data gathered in Bletchley Park for a longer (earlier) period, but maybe not shared anymore or not in full. This is a significant observation, and this is maybe how the report can be dated to be closer to June than September 1940. Or this is how the XYZ or Polish-French-English cooperation has slowly ended, and a new era of code breaking run and dominated by Britain alone has started.

Here is the documentary to watch:

  • English version “Enigma. We have got news (EN 2019)” is here,
  • French version “Enigma. Il y a du nouveau (FR 2019)” is here,
  • Polish version “Enigma. Mamy nowiny (PL 2019)” is here.
  • The Spanish version is here (was added in 2020).
  • The Italian version is here (was added in 2020).
  • The German version is here (added in 2020). 


On a picture: an original French-Polish made Enigma machine with ABCD keyboard from the collection of Pilsudski Institute in London. Only 2 such machines exist.

P.S. This report could be cited as follows:
Marian Rejewski, Henryk Zygalski and other undisclosed authors:
Kurzgefasste Darstellung der Auflösungsmethoden. Bertrand archives, Service Historique de la Défense, Vincennes, France, DE 2016 ZB 25/6, Dossiers Nos. 281 and 282, ca. 1940.

Added in 2020:

  • Links to new language versions of the documentary are added above.
  • Here are the exercises UCL students need to solve about breaking Enigma.
  • Here is a short synthetic document on one page about cryptanalysis of Enigma. 

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:


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


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 in few cases for the original DES S-boxes. In fact 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. Or that “some linear combination of output Boolean components is linear on an affine space of dimension 1 (a coset of a certain linear space)”.

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. This attack is no here, is now public.

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 strongly biased (in fact only when input b is fixed). If so either (W1+X1+Y1+Z1+R01) or (1+W1+X1+Y1+Z1+R01) would 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:


which is the same as:


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


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 exists however, and it was presented at ICISC 2019.

Some versions of DES are substantially wekaer, other are stronger. For example S^5DES has a lot more 1-weak normal annihilations, eight times more than with DES. In contrast, in more recent versions of DES, with DESL and in S*DES, there are zero such events whatsoever. 

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, Kossiakoff Centre, Laurel, MD, USA. Here is the program.

Added December 2019: Here are the  slides presented at ICISC conference in Seoul Korea, “Systematic Construction of Nonlinear Product Attacks on Block Ciphers”, on 4 December 2019.

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, on which accounts, most likely he is simply not guilty.

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.