Search

An important building block for many cryptographic systems is a random number generator. Random numbers are required in these systems, because they are unpredictable for potential attackers. These random numbers can either be generated by a truly random physical source (that is non-deterministic) or using a deterministic algorithm. In practical applications where relatively large amounts of random bits are needed, it is also possible to combine both of these generator types. A non-deterministic random number generator is used to provide a truly random seed, which is used as input for a deterministic algorithm that generates a larger amount of (pseudo-)random bits. In cryptographic systems where Physical Unclonable Functions (PUFs) are used for authentication or secure key storage, an interesting source of randomness is readily available. Therefore, we propose the construction of a FIPS 140-3 compliant random bit generator based on an SRAM PUF in this paper. These PUFs are a source of instant randomness, which is available when powering an IC. Based on large sets of measurements, we derive the min-entropy of noise on the start-up patterns of SRAM memories. The min-entropy determines the compression factor of a conditioning algorithm, which is used to extract a truly random (256 bits) seed from the memory. Using several randomness tests we prove that the conditioned seed has all the properties of a truly random string with full entropy. This truly random seed can be derived in a low cost and area efficient manner from the standard IC component SRAM. Furthermore, an efficient implementation of a deterministic algorithm for generating (pseudo-)random output bits will be proposed. Combining these two functions leads to an ideal way to generate large amounts of random data based on non-deterministic randomness.

In this paper we describe the results of our investigations Supported by EU FP7 project UNIQUE on the randomness and reliability of D flip-flops when used as a Physically Unclonable Function (PUF). These D flip-flops are hardware components which present a random start-up value when powered up. We show that against all odds, enough randomness exists in such elements when implemented on an Application-Specific Integrated Circuit (ASIC) to turn the responses of a number of D flip-flops into a secret random sequence allowing to derive keys for use in conjunction with cryptographic algorithms. In addition to being unpredictable, these flip-flops have the advantage that they can be spread over random locations in an ASIC. This makes them very difficult to reverse-engineer when used to hide a secret key in a design at a relatively small cost in resources.

Non-volatile memory is essential in most embedded security applications. It will store the key and other sensitive materials for cryptographic and security applications. In this chapter, first an overview is given of current flash memory architectures. Next the standard security features which form the basis of so-called secure memories are described in more detail. Smart cards are a typical embedded application that is very vulnerable to attacks and that at the same time has a high need for secure non-volatile memory. In the next part of this chapter, the secure memories of so-called flash-based high-density smart cards are described. It is followed by a detailed analysis of what the new security challenges for such objects are.

Cryptographic algorithm implementations are subject to specific attacks, called side channel attacks, focusing on the analysis of their power consumption or execution time or on the analysis of faulty computations. At FDTC06, Fumaroli and Vigilant presented a generic method to compute an exponentiation resistant against different side channel attacks. However, even if this algorithm does not reveal information on the secrets in case of a fault attack, it can not be used to safely implement a crypto-system involving an exponentiation. In this paper, we propose a new exponentiation method without this drawback and give a security proof of resistance to fault attacks. As an application, we propose an RSA algorithm implemented using the Chinese Remainder Theorem protected against side channel attacks. The exponentiation algorithm is also33% faster than the previous method.

In this paper we discuss memories with their basic protection mechanisms and the results of the evaluation of a modern high-density flash memory by an Information Technology Security Evaluation Facility (ITSEF). In a second part, we address the notion of Authenticated Flash and present some authentication methodologies used for existing Flash devices.

This paper discusses key recovery and universal forgery attacks on several MAC algorithms based on universal hash functions. The attacks use a substantial number of verification queries but eventually allow for universal forgeries instead of existential or multiple forgeries. This means that the security of the algorithms completely collapses once a few forgeries are found. Some of these attacks start off by exploiting a weak key property, but turn out to become full-fledged divide and conquer attacks because of the specific structure of the universal hash functions considered. Partial information on a secret key can be exploited too, in the sense that it renders some key recovery attacks practical as soon as a few key bits are known. These results show that while universal hash functions offer provable security, high speeds and parallelism, their simple combinatorial properties make them less robust than conventional message authentication primitives. © International Association for Cryptologic Research 2008. ispartof: pages:144-161 ispartof: Lecture Notes in Computer Science vol:5157 pages:144-161 ispartof: CRYPTO 2008 location:CA, Santa Barbara date:17 Aug - 21 Aug 2008 status: published

Over the past ten years, cryptographic algorithms have been found to be vulnerable against side-channel attacks such as power analysis attacks, timing attacks, electromagnetic radiation attacks and fault attacks. These attacks capture leaking information from an implementation of the algorithm in software or in hardware and apply cryptanalytical and statistical tools to recover the secret keys. A very well-known countermeasure against these attacks is to randomize every execution of the algorithm and every intermediate piece of data with a so-called masking method. In this paper we demonstrate that traditional countermeasures such as masking methodsfor symmetric cryptosystems are completely inefficient against fault attacks. In other words, differential fault attacks still apply on masked data. As an example we show how to recover secret keys from two masked AES implementations using a basic differential fault attack.

Secure embedded Devices for the mobile, financial and automotive markets require more and more security features to resist today’s field attacks. At the software level, side-channel attacks such as timing attacks, power attacks, electro-magnetic attacks and radio-frequency attacks on embedded devices have been described for a number of years now, and numerous adequate security countermeasures have been published and implemented by most manufacturers. At the hardware level, the story is completely different. Manufacturers have been aware of physical security issues and invasive/side-channel attacks for quite some time, but protecting embedded chips against such attacks requires quite some architectural knowledge and needs to be addressed at the design level. Countermeasures can hardly be added after the fact.

High Density cards represent the next generation of secure portable and removable tokens for the mobile and wireless markets. What makes these cards so particular is that, in addition to the traditional ISO 7816 interface to the Subscriber Identity Module, there are hundreds of megabytes of non-volatile Flash Memory available on the same token. This is a small revolution when compared to current EEPROM cards which allow for only a few hundreds of kilobytes of memory both for applications and data. Flash memory can be accessed either via a USB (Universal Serial Bus) or an MMC (MultiMediaCard) high speed interface. Therefore two different ecosystems co-exist on the same chip, which makes the security aspects of these cards particularly interesting and challenging.

Flash memory is a type of non-volatile semiconductor memory that can be electrically erased and programmed. It can be found in almost every high-capacity consumer electronic device in the market. Examples of such mass memory products include USB flash drives, digital cameras, mobile handsets, set-top boxes for Pay-TV applications, and many more. Some of them use NAND flash technology and others use NOR flash technology. To put it simply, NAND flash is the most adequate for mass-storage of user data because of its high speed access and because the organization of user data is usually error-tolerant (digital pictures, music) and NOR flash is more adequate for code-type data because of its highly reliable nature and its XIP (execute in place) capability, meaning that a program stored in NOR flash does not need to be transferred to RAM before being executed. When it comes to set-top boxes or handsets, manufacturers and operators are becoming increasingly security concerned. Conditional Access providers do not want to see their operating system and security codes dispatched over the internet and mobile phone operators fear that viruses or Trojan horses will eventually reach the handset platform. Thus new security features start appearing on those types of flash memory devices. Another sector which needs increasing data and program storage capacity is the smart card industry. Current high-end cards have a few hundred kilobytes of embedded ROM and EEPROM memory to hold their operating system and application data when several megabytes would ideally be required. The new high density smart cards will address such requirements in the near future by providing increased on-board storage capacity. The question then becomes how to reach the required security level operators expect for all these new devices.

This chapter contains sections titled: Introduction WLAN and WPAN Security GSM and 3GPP Security Mobile Platform Layer Security Hardware Attacks on Mobile Equipment Conclusion References ]]>

Stream Cipher Cryptanalysis -- An Improved Correlation Attack on A5/1 -- Extending the Resynchronization Attack -- A New Simple Technique to Attack Filter Generators and Related Ciphers -- Side-Channel Analysis -- On XTR and Side-Channel Analysis -- Provably Secure Masking of AES -- Block Cipher Design -- Perfect Diffusion Primitives for Block Ciphers -- Security of the MISTY Structure in the Luby-Rackoff Model: Improved Results -- FOX : A New Family of Block Ciphers -- Efficient Implementations -- A Note on the Signed Sliding Window Integer Recoding and a Left-to-Right Analogue -- Fast Irreducibility Testing for XTR Using a Gaussian Normal Basis of Low Complexity -- Modular Number Systems: Beyond the Mersenne Family -- Efficient Doubling on Genus Two Curves over Binary Fields -- Secret Key Cryptography I -- About the Security of Ciphers (Semantic Security and Pseudo-Random Permutations) -- A Subliminal Channel in Secret Block Ciphers -- Blockwise Adversarial Model for On-line Ciphers and Symmetric Encryption Schemes -- Cryptanalysis -- Cryptanalysis of a White Box AES Implementation -- Predicting Subset Sum Pseudorandom Generators -- Collision Attack and Pseudorandomness of Reduced-Round Camellia -- Cryptographic Protocols -- Password Based Key Exchange with Mutual Authentication -- Product Construction of Key Distribution Schemes for Sensor Networks -- Deterministic Key Predistribution Schemes for Distributed Sensor Networks -- On Proactive Secret Sharing Schemes -- Secret Key Cryptography II -- Efficient Constructions of Variable-Input-Length Block Ciphers -- A Sufficient Condition for Optimal Domain Extension of UOWHFs.SAC 2004 was the eleventh in a series of annual workshops on Selected Areas in Cryptography. This was the second time that the workshop was hosted by the University of Waterloo, Ontario, with previous workshops being held at Queen’sUniversityinKingston(1994,1996,1998and1999),CarletonUniversity in Ottawa (1995, 1997 and 2003), the Fields Institute in Toronto (2001) and Memorial University of Newfoundland in St. John’s (2002). The primary intent of the workshop was to provide a relaxed atmosphere in which researchers in cryptography could present and discuss new work on selected areas of current interest. This year’s themes for SAC were: – Design and analysis of symmetric key cryptosystems. – Primitives for symmetric key cryptography, including block and stream - phers, hash functions, and MAC algorithms. – E?cient implementation of cryptographic systems in public and symmetric key cryptography. – Cryptographic solutions for mobile (web) services. A record of 117 papers were submitted for consideration by the program committee. After an extensive review process, 25 papers were accepted for p- sentation at the workshop (two of these papers were merged). Unfortunately, many good papers could not be accommodated this year. These proceedings contain the revised versions of the 24 accepted papers. The revised versions were not subsequently checked for correctness. Also, we were very fortunate to have two invited speakers at SAC 2004. • Eli Biham arranged for some breaking news in his talk on “New Results on SHA-0 and SHA-1.” This talk was designated as the Sta?ord Tavares L- ture.

We consider how related-key attacks can be mounted on the IBM 4758 cryptoprocessor, and also show that its EDEx multiple mode is far less secure than one could believe. As few as about 232 known plaintexts and related-key known ciphertexts in the first case, and 234 chosen ciphertexts in the second case are required to mount key-recovery attacks. These results show that seemingly academic attacks seriously need to be taken into consideration when it comes to real-life implementations.

Physical unclonable functions based on static RAM can help provide new approaches to such applications as secure key storage, secure boot for flash-memory-based embedded devices without on-chip nonvolatile memory, hardware-software binding, and generating true random numbers. Part 1 is available at http://doi.ieeecomputersociety.org/10.1109/MSP.2012.68.

This paper considers arbitrary-length chosen-ciphertext secure asymmetric encryption, thus addressing what is actually needed for a practical usage of strong public-key cryptography in the real world. We put forward two generic constructions, gem-1 and gem-2 which apply to explicit fixed-length weakly secure primitives and provide a strongly secure (IND-CCA2) public-key encryption scheme for messages of unfixed length (typically computer files). Our techniques optimally combine a single call to any one-way trapdoor function with repeated encryptions through some weak block-cipher (a simple xor is fine) and hash functions of fixed-length input so that a minimal number of calls to these functions is needed. Our encryption/decryption throughputs are comparable to the ones of standard methods (asymmetric encryption of a session key + symmetric encryption with multiple modes). In our case, however, we formally prove that our designs are secure in the strongest sense and provide complete security reductions holding in the random oracle model.

Although tamper-resistant devices are specifically designed to thwart invasive attacks, they remain vulnerable to micro-probing. Among several possibilities to provide data obfuscations, keyed hardware permutations can provide compact design and easy diversification. We discuss the efficiency of such primitives, and we give several examples of implementations, along with proofs of effectively large key-space.

This paper analyses the cryptographic hash function SHA- 1 in encryption mode. A detailed analysis is given of the resistance of SHA-1 against the most powerful known attacks today. It is concluded that none of these attacks can be applied successfully in practice to SHA-1. Breaking SHA-1 in encryption mode requires either an unrealistic amount of computation time and known/chosen texts, or a major breakthrough in cryptanalysis. The original motivation for this analysis is to investigate a block cipher named SHACAL based on these principles. SHACAL has been submitted to the NESSIE call for cryptographic primitives.

This paper intends to provide information about up-to-date performances of smart-card arithmetic coprocessors regarding major public-key cryptosystems and analyze the main tendences of this developing high-tech industry and related markets. We also comment hardware limitations of current technologies and provide a technique for extending them by virtually doubling their capacities.

Wagner, Goldberg and Briceno have recently published an attack [2] on what they believe to be Comp128, the GSM A3A8 authentication function [1]. Provided that the attacker has physical access to the card and to its secret PIN code (the card has to be activated), this chosen plaintext attack recovers the secret key of the personalized SIM (Secure Identification Module) card by inducing collisions on the second (out of 40) round of the compression function. In this paper we suggest two different approaches to strengthen the alleged Comp128 algorithm with respect to this attack. An evaluation of the number of chosen plaintexts and the new complexity of the attack are given.

This paper describes a new type of attack on tamper-resistant cryptographic hardware. We show that by locally observing the value of a few RAM or adress bus bits (possibly a single one) during the execution of a cryptographic algorithm, typically by the mean of a probe (needle), an attacker could easily recover information on the secret key being used; our attacks apply to public-key cryptosystems such as RSA or El Gamal, as well as to secret-key encryption schemes including DES and RC5.

The DES has reached the end of its lifetime due to its too short key length and block length (56 and 64 bits respectively). As we are awaiting the new AES, triple land double) encryption are the common solution. However, several authors have shown that these multiple modes are much less secure than anticipated. The general belief is that these schemes should not be used, as they are not resistant against attacks requiring 2(64) chosen plaintexts. This paper extends the analysis by considering some more realistic attack models. It also presents an improved attack on multiple modes that contain an OFB mode and discusses practical solutions that take into account realistic constraints. ispartof: pages:215-230 ispartof: Lecture Notes in Computer Science vol:1636 pages:215-230 ispartof: FSE 1999 location:ITALY, ROME date:24 Mar - 26 Mar 1999 status: published

One of the key directions in complexity theory which has also filtered through to cryptographic research, is the effort to classify related but seemingly distinct notions. Separation or reduction arguments are the basic means for this classification. Continuing this direction we identify a class of problems, called "matching problems," which are related to the class of "decision problems." In many cases, these classes are neither trivially equivalent nor distinct. Briefly, a "decision" problem consists of one instance and a supposedly related image of this instance; the problem is to decide whether the instance and the image indeed satisfy the given predicate. In a "matching" problem two such pairs of instances-images are given, and the problem is to "match" or "distinguish" which image corresponds to which instance. Clearly the decision problem is more difficult, since given a "decision" oracle one can simply test each of the two images to be matched against an instance and solve the matching problem. Here we show that the opposite direction also holds, presuming that randomization of the input is possible, and that the matching oracle is successful in all but a negligible part of its input set. We first apply our techniques to show equivalence between the matching Diffie-Hellman and the decision Diffie-Hellman problems which were both applied recently quite extensively. This is a constructive step towards examining the strength of the Diffie-Hellman related problems. Then we show that in cryptosystems which can be uniformly randomized, non-semantic security implies that there is an oracle that decides whether a given plaintext corresponds to a given ciphertext. In the process we provide a new characteristic of encryption functions, which we call "universal malleability."

This paper describes a timing attack on the RC5 block encryption algorithm. The analysis is motivated by the possibility that some implementations of RC5 could result in the data-dependent rotations taking a time that is a function of the data. Assuming that encryption timing measurements can be made which enable the cryptanalyst to deduce the total amount of rotations carried out during an encryption, it is shown that, for the nominal version of RC5, only a few thousand ciphertexts are required to determine 5 bits of the last half-round subkey with high probability. Further, it is shown that it is practical to determine the whole secret key with about 220 encryption timings with a time complexity that can be as low as 228.

SEAL was first introduced in [1] by Rogaway and Coppersmith as a fast software-oriented encryption algorithm. It is a pseudorandom function which stretches a short index into a much longer pseudorandom string under control of a secret key pre-processed into internal tables. In this paper we first describe an attack of a simplified version of SEAL, which provides large parts of the secret tables from approximately 224 algorithm computations. As far as the original algorithm is concerned, we construct a test capable of distinguishing SEAL from a random function using approximately 230 computations. Moreover, we describe how to derive some bits of information about the secret tables. These results were confirmed by computer experiments.

DES and triple-DES are two well-known and popular encryption algorithms, but they both have the same drawback : their block size is limited to 64 bits. While the cryptographic community is working hard to select and evaluate candidates and finalists for the AES (Advanced Encryption Standard) contest launched by NIST in 1997, it might be of interest to propose a secure and simple double block-length encryption algorithm. More than in terms of key length and block size, our Universal Encryption Standard is a new construction that remains totally compliant with DES and triple-DES specifications as well as with AES requirements.

This paper details the attack on RC6 which was announced in a report published in the proceedings of the second AES candidate conference (March 1999). Based on an observation on the RC6 statistics, we show how to distinguish RC6 from a random permutation and to recover the secret extended key for a fair number of rounds.

International audience; We revisit the problem of Full Disk Encryption (FDE), which refers to the encryption of each sector of a disk volume. In the context of FDE, it is assumed that there is no space to store additional data, such as an IV (Initialization Vector) or a MAC (Message Authentica-tion Code) value. We formally define the security notions in this model against chosen-plaintext and chosen-ciphertext attacks. Then, we classify various FDE modes of operation according to their security in this setting, in the presence of various restrictions on the queries of the adversary. We will find that our approach leads to new insights for both theory and practice. Moreover, we introduce the notion of a diversifier, which does not require additional storage, but allows the plaintext of a particular sector to be encrypted to different ciphertexts. We show how a 2-bit diversifier can be implemented in the EagleTree simulator for solid state drives (SSDs), while decreasing the total number of Input/Output Operations Per Second (IOPS) by only 4%.