Symmetric Key Ciphers for FHE

In recent years, small devices with limited storage and computing power have acquired more and more popularity. This phenomenon, together with the appearance of cloud services that offer extensive storage and high computing power, has made computation outsourcing a key application to study. This setting, where a user with limited resources stores data on a remote server and also asks this server to make some computation on his behalf, comes together with new challenges and concerns related to privacy and security.

A simple scenario

The user Alice encrypts her data under a homomorphic encryption scheme and sends the ciphertexts to the server (eg. cloud). Now the server computes some function (eg. mean value) on Alice's encrypted data and sends back an encryption of the result, which can be decrypted by Alice with the appropriate key. Despite its simplicity, this model still requires a lot of effort from the user. In fact, all the FHE schemes that we know of have very large keys and heavy encryption overhead. The most natural approach is then trying to free the user from the burden of complex homomorphic computations, by asking her to do only the key generation part, the symmetric encryption and the final decryption, while leaving all the rest to the powerful server.

A hybrid framework

The user Alice generates a secret key $sk^S$ for a symmetric encryption scheme, a pair $(pk^H, sk^H)$ for a homomorphic public key encryption scheme, and sends $pk^H$ to the server together with an encryption of $sk^S$ under $pk^H$. Then, Alice encrypts her data under the symmetric encryption scheme and sends the resulting ciphertexts to the server, which homomorphically evaluates the decryption circuit of the symmetric encryption scheme, thus obtaining ciphertexts under the homomorphic scheme. This last operation can be seen as a sort of bootstrapping (from one scheme to another one), but does not involve any circular security assumption. At this point, the server can homomorphically compute a certain function $f$ on the resulting ciphertexts and send back the result, encrypted under the homomorphic encryption scheme. Alice can finally recover the result thanks to her $sk^H$.

Despite numerous improvements in recent years FHE remains highly unpractical, and one of the main problems is limited homomorphic capacity. In fact, all the FHE schemes we know of contain a noise term that grows with homomorphic operations. The homomorphic capacity corresponds to the amount of computation that can be performed before having to ``refresh'' the ciphertext via the expensive operation of bootstrapping. It is thus of vital importance to manage the error growth during homomorphic operations.

State-of-the-art ciphers

AES is a natural benchmark for FHE implementations. The homomorphic evaluations of some lightweight block ciphers such as SIMON have been investigated by Lepoint and Naehrig as well. It turns out that there is much room for improvement in optimizing the multiplicative depth. In this direction, many dedicated symmetric key ciphers with low-noise ciphertexts have been proposed.

• In 2015, Albrecht et al presented a flexible block cipher LowMC, which is based on an SPN structure with $80,128$ and $256$-bit key variants. The design philosophy is to minimize the multiplicative complexity, which is more relevant in the multi-party computation context. It also has very low multiplicative depth compared with existing block ciphers.

  Later, Dinur et al mounted optimized interpolation attacks against some instances of LowMC. More precisely, some $80$-bit key instances could be broken $2^{23}$ times faster than exhaustive search and all instances that are claimed to provide $128$-bit security could be broken about $1000$ times faster than exhaustive search. These attacks show that the ciphers do not provide the expected security level. The cryptanalysis also led to a revised version of LowMC.
• Keyvrium was designed by Canteaut et al and is a stream cipher aiming at $128$-bit security. It is based on the lightweight stream cipher Trivium, which has $80$-bit security. Trivium and Keyvrium both achieve similar multiplicative depth compared to instances of LowMC. They have a smaller latency than LowMC, but have a slightly smaller throughput.
• The FLIP family stream ciphers proposed by Méaux et al have the lowest depth compared with previous ciphers. Several versions are provided including $80$-bit and $128$-bit security instantiations. The main design principal is to filter a constant key register with a time-varying public bit permutation, which allows for small and constant noise growth. However, FLIP has a much higher number of ANDs per encrypted bit than the above ciphers.

To sum up, blending symmetric ciphers and FHE is definitely an interesting idea that could prove fundamental for bringing homomorphic encryption in the real world.

The other fellows also made contributions to this blog post.

WhatsApp backdoor? Should I be worried?

WhatsApp Backdoor!!! 

Let's start this blog entry with that title and it is very easy to get reader's attention (Especially in the security community) with big bold letters and saying that there is a backdoor. I say this because it was exactly what happened on January 13th (Friday the 13th, maybe it is correlated) when The Guardian released the news. After that, the security community/websites and others started a big debate about it. In fact, some hours after the release from the Guardian others websites started saying that it isn't a backdoor such as: Gizmodo, Open Whisper System blog and others' websites.

Well, we are going to give some "conclusions about the subject" later. First, let's explore more about it.

What is a backdoor?

If we talk about computer systems or cryptography, we are going to have something like this definition: "A backdoor is a method, often secret, of bypassing normal authentication in a product, computer system, cryptosystem or algorithm etc. Backdoors are often used for securing unauthorized remote access to a computer, or obtaining access to plaintext in cryptographic systems." In other words, it is an easy way to obtain access.

Are backdoors common?

Unfortunately, yes it appears in the news and computer systems more than we want. Also, after the Snowden revelations the term backdoor is very common in the non-academic area. However, it does not mean that people become more worried.

What is the real problem?

Perfect, we learned about backdoors. Now, let's explain the problem with WhatsApp. Let's see an hypothetical case, imagine that you have a smartphone and for some reason (fall in a lake, you have been abducted by E.T. and forget your phone in the spaceship) you don't have access to your smartphone anymore. Fortunately, you can recover your phone number, buy a new smartphone and reinstall Whatsapp. However, when you reinstall WhatsApp, it generates a new key. However, now we have a problem what the app should do with the messages that you received when you were offline. The app could just drop the messages and never deliver or it could ask for your contacts to encrypt with the new key. According to the Guardian this approach is the backdoor:
"WhatsApp’s implementation automatically resends an undelivered message with a new key without warning the user in advance or giving them the ability to prevent it."

I, personally, say that it is a mistake that WhatsApp just show a notification saying that the key change and automatically resends.

Is it exploitable?

I will say: Yes, it is.
Let's see how it is possible to exploit.

In fact, it consists in exploit another vulnerability, it is present in the SS7 protocol. The Signalling System No. 7 (SS7) is a set of telephony signaling protocols developed in 1975, which is used to set up and tear down most of the world's public switched telephone network (PSTN) telephone calls. It also performs number translation, local number portability, prepaid billing, Short Message Service (SMS), and other mass market services.

The SS7 vulnerabilities are known since 2008. However, it had the attention from media in 2014, Tobias Engel at CCC showed how it is possible to exploit SS7 vulnerabilities. You can check exactly how in this link. In the video, he shows that it is possible to change the phone number between cellphones. In the same congress and right after Tobias, Karsten Nohl showed how to read "others SMS", the talk can be followed in this link.

What is the SS7 vulnerability?

Let see very quickly the structure of a GSM network, the next figure shows it.

So, if you are inside of the SS7 network, you can just start listen the network and as we saw in the videos it is possible to change somethings such as your number.

Since it is possible to change your number and the verification from whatsApp can be done by call or a SMS verification. What happened if I have access to SS7 network and change my number to any other number and I reinstall WhatsApp and pass the verification?

According to the policy of WhatsApp, my smartphone is going to generate a new key and all the new messages are going to be encrypted with this new key. I didn't create a new attack here, it has been done before as this youtube video shows:

It is valid to say that this attack can be used in others messengers. However, others apps have another policy, e.g.  Signal drops the messages until you "recheck" the new key.

 If you are interested to see the how messengers handle this key problem, there is a nice blog entry at Medium.

Conclusions? 

The news from Guardian is not a real backdoor, it is a known problem about handling with keys and the news was more like a "click bait". However, the good thing about all of this history are the discussions in different communities and an alert to people take care about their privacy.

All this incident makes us to start doing some social and technical questions, such as:
Should we accept the news from the media as truth?
Why the hell we continue to use a system from 1975?
Can we create a better way to handle with keys?


 In addition, I should say that if you are looking for more privacy to your life. You should check Privacy Tools, in this case, the section about "Encrypted Instant Messenger".
 

RWC 2017 - Post-quantum cryptography in the real-world

A new year takes off and, along with it, thousands of resolutions are formulated. Although I am not the right person to talk about them (my diet will begin next Monday), I wish to discuss a resolution that the cryptographic community as a whole has set for itself in this 2017. Because that's what people do at Real World Crypto (RWC): they talk about new threads, topics could be worth exploring during the new year, directions for their researches and interests. This year, for the first time in RWC, post-quantum cryptography (PQC) was given an entire session, clear sign that time is changing and the moment has come to bring the discussion to the real world. The message is clear: even if quantum computers are not popping up in tomorrow's newspapers, we can't postpone any longer.

A very simple reason for this was given by Rene Peralta, of the NIST PQC team, during the overture of the session: standardisation takes time, up to seven years if we start right now, and full transition takes even longer. I found Rene's presentation to be neat and direct: our public-key cryptography fails against quantum computers and our symmetric one needs some (non-drastic) modifications. The resolution is to "start thinking about it this year, possibly by November 30^th, 2017". However, a question arises quite naturally: are we ready?

The other three talks of the session tried to answer in the affirmative. Among the several PQC proposals that are around in theoretical papers, two made their ways into RWC: the well-stablished lattice-based cryptography and the new-born isogeny-based cryptography, which nevertheless carries the pride and sympathy of ECC.

Lattices and funny names: NewHope and Frodo and Crystals

Lattice-based cryptography has three representatives in the run for PQC schemes. Valeria Nikolaenko showed two: the first one is called NewHope and is a key agreement protocol based on the hardness of Ring-LWE. The latter is a problem very favourable to applications because it combines sound theoretical security (worst-case to average-case reduction) to fast implementations thanks to specific choices of parameters which allow for speed-ups in the computations: NewHope turns out to be even faster than ECC and RSA, but at the price of a larger communication. However, there are some concerns on the security of LWE when the ring structured is added. Thus, Frodo ("take off the ring") is designed to achieve the same goal using only standard LWE. The drawback is a degradation in performance, since the tricks hinted above cannot be used anymore and keys are generally bigger.

The third lattice-based scheme was presented by Tancrede Lepoint and is a suite called Crystals. This is based on yet another kind of lattices: module lattices, for which it is also known a worst-case to average-case reduction. These are less structured lattices (hence possibly calming down the detractors of ring structure) in which similar implementation speed-ups are possible: the timing is indeed comparable to NewHope's, while the communication is improved.

"Make elliptic curves great again"

Michael Naehrig presented a new proposal for PQC: do you remember curves with plenty of small subgroups where to easily solve the discrete logarithm problem? Now they come in handy again: all the subgroups (of order 2 and 3) are considered to be nodes of a graph, whose edges are the isogenies (a.k.a. bijetive homorphisms between curves). In this new context, given two curves in the graph, it is difficult to come up with the isogeny linking the two. However, such a new approach doesn't really stand against other solutions: keys are small but performance is not a pro (so to speak).

[The same blog post appeared here.]