Category Archives: Technology

Quantum what?

Posted on by
2

Quantum what?

Quantum computing, quantum cryptography, and post-quantum cryptography: these terms are confusing.  This post attempts to clarify them and draws the relationship between them.

Quantum computing is the set of technologies that use quantum-mechanical phenomena to perform computing.  Quantum computing uses qubits rather than bits.  Where one bit of conventional computing has one of the two possible states “0” or “1”, a qubit has a set of independent states simultaneously via superposition.  Furthermore, entangled qubits behave together in non-conventional ways (for instance, immediate synchronization independent from the distance separating the two qubits).

These properties allow solving some classes of problems, many orders faster than conventional computing.  In 1994, Peter Shor published “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” [1].  His algorithm solves the prime factorization and discrete logarithm hard problems.  Prime factorization is the foundation of cryptosystems such as Diffie Hellman (DH) and RSA.  Discrete logarithms are the foundation of elliptic curve cryptosystems (ECC). In 1996, Lov Grover published “A fast quantum mechanical algorithm for database search” [2].  His algorithm inverts one-way functions in  time.  It applies to symmetric ciphers and cryptographic hashes.

Whenever quantum computing is operational, accurate, and with enough qubits, these algorithms and their enhancements will impact traditional cryptography.  To mitigate Grover’s algorithm, the size of symmetric keys and hashes has to increase.  For instance, AES will need at least 256-bit keys. Shor’s algorithm annihilates the security of prime factorization or discrete logarithm-based cryptosystems.  In other words, DH, RSA, and ECC will not be secure anymore.

Post-quantum cryptography encompasses the algorithms that are allegedly immune against quantum computing.   There are mainly four categories of algorithms.

  • Hash-based signatures; It uses the current hash algorithms, and its security is well understood. The size of the public key is far larger and usable only once. 
  • Code-based encryption;  It uses sophisticated error-correcting codes.  The McEliece’s scheme was first proposed in 1978 [3] and has not been broken since. 
  • Lattice-based encryption is the most efficient and promising solution.  It allows encryption, digital signatures, and fully homomorphic encryption.
  • Multi-variate Quadratic Equations seem the less promising path.  All proposed schemes are currently broken. 

It is wise to strengthen post-quantum cryptography to be ready whenever this threat is active.  NIST estimates that a 1 billion $ quantum computer may break RSA 2048 keys in a matter of hours.   A future post will explore more in detail post-quantum cryptography.

Quantum cryptography or Quantum Key Distribution (QKD) sends over information, including a secret key, using photons over a line between Alice and Bob.  Once Bob received the secret key, Alice and Bob use it to encrypt and decrypt via traditional symmetric cryptosystems their messages.  This key distribution is very similar to many current systems.  Nevertheless, due to the Heisenberg’s principle, if Eve eavesdrops the QKD, she alters the secret key.  Thus, Alice and Bob know they are eavesdropped, offering higher security.  The obvious limitation is that it can only be used in point to point communications.  The first QKDs were designed in the 80s.

Hoping that this post shed some light, I wish you a happy new year.

References

[1]          P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM J. Comput., vol. 26, no. 5, pp. 1484–1509, Oct. 1997, doi: 10.1137/S0097539795293172.

[2]          L. K. Grover, “A fast quantum mechanical algorithm for database search,” ArXivquant-Ph9605043, Nov. 1996.

[3]          R. McEliece, “A public-key cryptosystem based on algebraic coding theory,” NASA, DSN 42-44, 1978.

Apple’s Find My

Posted on by
Reply

Apple disclosed at the WWDC an interesting feature: “Find My.”   It will be possible to track the GPS location of your device if it is stolen or lost.  And Apple will not know this location.  Here is how it works. 

The prerequisite is that you have at least two Apple devices.   All your devices share a private key.  The trick is that instead of having one unique public key, the devices have a multitude of public keys linked to this private key.  This is possible, and there are numerous known cryptographic solutions that may fulfill this part.

The device broadcasts via Bluetooth its current public key.   The device broadcasts this beacon even while turned out.  Any Apple device nearby may catch the beacon.  Then the receiving device encrypts its current GPS location with the broadcast public key.  It sends the encrypted location as well as the cryptographic hash of the public key to Apple’s server.  Of course, the public key changes periodically.  The rotating period has not been disclosed.

If you want to locate one of your devices, you trigger the request on one of your devices.  It sends the hash of the public key to the Apple server, which returns the encrypted location.  The device has the private key and thus can decrypt the location. Et voila.

Of course, under the assumption that Apple does not have the private key, only your devices can decrypt the location.  Normally, Apple can neither get the location nor link different related public keys together.

Many questions that were not answered in the presentation.  The frequency of key rotation, is there a limited number of public keys, how to know which hash to send?  Waiting for some publications to deep dive.

The idea is interesting.  It is complex, thus subject to failures and vulnerabilities.   What would the system do if, from many locations, there is a beacon broadcasting the same public key?  Will the collection of multiple related public keys not reveal some partial information, for instance one of the exponents?

Biometric Vein Recognition Hacked

Posted on by
Reply

Biometric vein recognition is considered with iris recognition as the most secure biometrics system. Vein recognition is used in highly secure areas. Automatic Telling Machines starts to use this technology with, for instance in Japan. This statement was valid until December 2018. At the famous German Chaos Communication Congress (35c3), Krissler Ian, also known as Starbug, and Albrecht Julian demonstrated a method (German video) to create a lure hand that defeats commercial systems.

Starbug is a well known hacker in the field of biometrics. For instance, in 2016, he faked successfully the fingerprints of a German minister using high resolution captured photos.

For about 20 years, vein recognition is mainly a Japanese technology. Fujitsu and Hitachi are the two leaders. The network of veins is captured either by reflection from the palm or through transparency with Infra Red (IR) light for fingers. The captured network is turned into minutiae like a typical fingerprint.

The capture phase seems rather simple. The researchers removed the IR filter of a traditional high-end DSLR camera (in that case, Nikon D600) with good lenses. They were able to get a proper capture up to 6 meters with a flash. They also built a raspberry-based system that could be hidden into a device, for instance, a hand-dry-blower. The captured image is processed via a python script to generate a skeleton of the network of veins (as illustrated by the figure below).

Once the skeleton available, they build a fake hand (or finger) using bee wax. The fake hand covers the printed picture. They tried many different materials, but the wax presented the best performance concerning transparency and diffraction of IR light, in other words, it better emulated skin.

Once the fake hand available, the attacker has to use it on the detector. They performed a live demonstration. The demonstration highlighted that the lighting conditions were critical. The strong lighting of the scene spoiled the demonstration, and they had to shade the detector to success. On the other hand, the fake finger detection went on smoothly. The detector was a kind of tunnel. At the time of the presentation, Hitachi and Fujitsu did not have yet reacted.

The attacked detectors had no liveliness detection. As I highlighted in section 7.4.2 of “Ten Laws for Security,” detecting the presence of a real living being behind the captured biometrics is necessarily for robust systems. Unfortunately, such detection increases the complexity and cost of detectors.

Conclusion: Once more, Law 1: Attackers will always find their way
was demonstrated.

Watermarking Deep Neural Networks

Posted on by
Reply

Recently, an IBM team presented at ASIA CCS’18 a framework implementing watermark in a Deep Neural Network (DNN) network. Similarly, to what we do in the multimedia space, if a competitor uses or modifies a watermarked model, it should be possible to extract the watermark from the model to prove the ownership.

In a nutshell, the DNN model is trained with the normal set of data to produce the results that everybody would expect and an additional set of data (the watermarks) that produces an “unexpected” result that is known solely to the owner. To prove the ownership, the owner injects in the allegedly “stolen” model the watermarks and verifies whether the observed result is what it expected.

The authors explored thee techniques in the field of image recognition:

  • Meaningful content: the watermarks are modified images, for instance by adding a consistently visible mark. The training enforces that the presentation of such visible mark results in a given “unrelated” category.
  • Unrelated content: the watermarks are images that are totally unrelated to the task of the model; normally they should be rejected, but the training will enforce a known output for the detection
  • Noisy content: the watermarks are images that embed a consistent shaped noise and produce a given known answer.

The approach is interesting. Some remarks inherited from the multimedia space:

  • The method of creating the watermarks must remain secret. If the attacker guesses the method, for instance that the system uses a given logo, then the attacker may perhaps wash the watermark. The attacker may untrain the model, by supertraining the watermarked model with generated watermarks that will output an answer different from the one expected by the original owner. As the attacker has uncontrolled, unlimited access to the detector, the attacker can fine tune the model until the detection rate is too low.
  • The framework is most probably too expensive to be used for making traitor tracing at a large scale. Nevertheless, I am not sure whether traitor tracing at large scale makes any sense.
  • The method is most probably robust against an oracle attack.
  • Some of the described methods were related to image recognition but could be ported to other tasks.
  • It is possible to embed several successive orthogonal watermarks.

A paper interesting to read as it is probably the beginning of a new field. ML/AI security will be key in the coming years.

Reference

Zhang, Jialong, Zhongshu Gu, Jiyong Jang, Hui Wu, Marc Ph. Stoecklin, Heqing Huang, and Ian Molloy. “Protecting Intellectual Property of Deep Neural Networks with Watermarking.” In Proceedings of the 2018 on Asia Conference on Computer and Communications Security, 159–172. ASIACCS ’18. New York, NY, USA: ACM, 2018. https://doi.org/10.1145/3196494.3196550.

French users seem aware of the risks and threats of illicit sites

Posted on by
Reply

The French HADOPI recently published an interesting paper “Etude sur les risques encourus sur les sites illicites,” i.e., a study on the risks incurred on illegal sites. They polled 1,021 Internet users older than 15. The first part of the study analyses the reported use of so-called illicit sites. The second part checks the awareness of these users of the associated risks.

The first part is very conventional and shows information that was already known for other markets. The results are neither surprising nor widely deviating from other countries. For instance, without surprise, the younger generations use more illicit sharing sites than the oldest ones.

Figure extracted from the report. In black, my proposed translation.

Music, movies and TV shows are the categories that are the most illicitly accessed.

The second part is more interesting than the first one. Most polled users claim to know the threats of Internet (scareware, spam, the slowdown of computer due to malware, adult advertisement, and change of browser’s settings) as well as the issues (theft of banking account, identity theft, scam, or ransomware). Nevertheless, the more using illicit content, the higher the risk of nuisance and prejudice. Not surprisingly, 60% of consumers who stopped using illicit content suffered at least on serious prejudice.

Figure extracted from the report. In black, my proposed translation.

Users seem to understand that the use of illicit content seriously increases the risks. Nevertheless, there is a distortion. The nuisance is more associated to illegal consumption than actual real prejudices.

Figure extracted from the report. In black, my proposed translation

The top four motivation of legal users is to be lawful (66%), fear of malware (51%), respect for the artists (50%) and a better product (43%). For regular illicit users, the top three motivation to use legal offer is a better quality (43%), fear of malware (42%) and being lawful (41%). 57% of illicit users claim that they intend to reduce or stop using illegal content. 39% of illicit users announce that they will not change their behavior. 4% of illicit users claim they plan to consume more illicit content.

We must always be cautious with the answers to a poll. Some people may not be ready to disclose their unlawful behavior. Therefore, the real values of illicit behavior are most probably higher than disclosed in the document. Polled people may also provide wrong answers. For instance, about 30% of the consumers is illicitly consuming software claim to use streaming! Caution should also apply to the classification between streaming and P2P. Many new tools, for instance, Popcorn time, use P2P but present a behavior similar to streaming.

Conclusion of the report

Risks are present on the Internet. Illicit users are more at risk than lawful users.

Users acknowledge that illicit consumption is riskier than legal consumption.

Legal offer is perceived as the safe choice.

Having been hit by a security problem pushes users towards the legal offer.

An interesting report, unfortunately, currently it is only available in French.

 

 

White box cryptography: an open challenge

Posted on by
2

The ideal implementation of a cryptographic algorithm would be such that even if the attacker would have the source code and would entirely control the platform, she would not be able to retrieve the secret key. In 2002, Stanley Chow and his colleagues proposed a new concept coined the white-box cryptography. The threat model of white-box attack assumes that the attacker has full access to the encryption software and entirely controls the execution platform. White-box cryptography attempts to protect the keys even under such a hostile threat model. The main idea is to create a functionally equivalent implementation of the encryption or decryption algorithm that uses only look-up tables. Corresponding look-up tables, with the corresponding hard-coded secret key, replace the S-boxes, Feistel boxes and XOR functions usually employed by symmetric cryptography. Then, the look-up tables are further randomized. In theory, the randomization hides the hard-coded key. White box cryptography is a difficult challenge for skilled reverse engineers.

Abundant cryptographic analysis has demonstrated that these constructions are not theoretically secure. Nevertheless, well-crafted real implementations may resist reverse engineering. Many vendors offer such white-box cryptography for AES. The issue is how do you know whether an implementation is robust. Securing white-box cryptography is a lot of black magic. Currently, the only solutions are either reverse-engineer it yourself or trust your supplier blindly.

Fortunately, the European-funded research project ECRYPT launches an exciting challenge: The WhiBox contest. It is a capture the flag challenge dedicated to white-box cryptography. Developers are encouraged to post AES-128 white-box implementation as a C source code. Attackers are invited to break the challenge, i.e., extract the encryption key.

The contest starts on May 15 and ends August 31. The winners, i.e., the implementation that resisted the longest, and the attacker who broke the “strongest” implementation, during the rump session of CHES 2017.

This initiative is interesting. It will be a benchmark of state of the art in this obscure field. Of course, it will have value only if enough skilled attackers will answer the challenge. I expect some success. It reminds the challenges to evaluate oracle attacks for digital video watermarking (BOWS and BOWS2). BOWS demonstrated the risk associated with the access to a watermark detector.

We will follow this challenge. Will commercial solutions dare to submit implementations? Winning this challenge would be a feather in their hat.

 

Reference:

    Chow, S., Eisen, P., Johnson, H., Oorschot, P.C. van: A White-Box DES Implementation for DRM Applications. In: Feigenbaum, J. (ed.) Digital Rights Management. pp. 1–15. Springer Berlin Heidelberg (2003).