International Association for Cryptologic Research

IACR News Central

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2015-02-27
22:17 [Pub][ePrint]

In this paper we analyze the general class of functions underlying the SIMON block cipher. In particular, we derive efficiently computable and easy to implement expressions for the exact differential and linear behavior of SIMON-like round function. Using those expressions we investigate a large set of natural SIMON variants with respect to the most important cryptographic criteria. Interestingly, the NSA\'s choice for the parameters are not always optimal.

Using a computer aided approach based on SAT/SMT solvers we are able to find both the optimal differential and linear characteristics for variants of SIMON and can also give better estimates on the

probability of differentials. As a result of this analysis we propose different sets of rotation constants, which feature better properties on some criteria, and might be interesting for further analysis.

22:17 [Pub][ePrint]

Feistel structures are an extremely important and extensively researched type of cryptographic schemes. In this paper we describe improved attacks on Feistel structures with more than 4 rounds.

We achieve this by a new attack that combines the main benefits of

meet-in-the-middle attacks (which can reduce the time complexity by

comparing only half blocks in the middle) and dissection attacks (which can reduce the memory complexity but have to guess full blocks in the middle in order to perform independent attacks above and below it). For example, for a 7-round Feistel structure on n-bit inputs with seven independent round keys of n/2 bits each), a MITM attack can use (2^1.5n ,2^1.5n) time and memory, while dissection requires (2^2n, 2^n) time and memory. Our new attack requires only (2^1.5n, 2^n) time and memory, using a few known plaintext/ciphertext pairs. When we are allowed to use more known plaintexts, we develop new techniques which rely on the existence of multicollisions and differential properties deep in the structure in order to further reduce the memory complexity.

Our new attacks are not just theoretical generic constructions - in fact, we can use them to improve the best known attacks on several concrete cryptosystems such as CAST-128 (where we reduce the memory complexity from 2^111 to 2^64) and DEAL-256 (where we reduce the memory complexity from 2^200 to 2^144), without affecting their time and data complexities. An extension of our techniques applies even to some non-Feistel structures - for example, in the case of FOX, we reduce the memory complexity of all the best known attacks by a factor of 2^16.

22:17 [Pub][ePrint]

Hardware and software of secured embedded systems are prone to physical attacks.

In particular, fault injection attacks revealed vulnerabilities on the data and the control flow

allowing an attacker to break cryptographic or secured algorithms implementations.

While many research studies concentrated on successful attacks on the data flow, only a few targets the instruction flow.

In this paper, we focus on electromagnetic fault injection (EMFI) on the control flow,

especially on the instruction cache.

We target the very widespread (smartphones, tablets, settop-boxes, health-industry monitors and sensors, etc.) ARMv7-M architecture.

We describe a practical EMFI platform and present a methodology providing high control level and high reproducibility over fault injections.

Indeed, we observe that a precise fault model occurs in up to 96\\% of the cases.

We then characterize and exhibit this practical fault model on the cache that is not yet considered in the literature.

We comprehensively describe its effects and show how it can be used to reproduce well known fault attacks.

Finally, we describe how it can benefits attackers to mount new powerful attacks or simplify existing ones.

22:17 [Pub][ePrint]

We present a side-channel attack based on remanence decay in volatile memory and show how it can be exploited effectively to launch a non-invasive cloning attack against SRAM PUFs --- an important class of PUFs typically proposed as lightweight security primitive with low overhead by using the existing memory of the underlying device. We validate our approach against two SRAM PUF implementations in 65~nm CMOS ASICs. We discuss countermeasures against our attack and propose the constructive use of remanence decay to improve the cloning-resistance of SRAM PUFs.

Moreover, as a further contribution of independent interest, we show how to use our evaluation results to significantly improve the performance of the recently proposed TARDIS scheme, which is based on remanence decay in SRAM and used as a time-keeping mechanism for low-power clock-less devices.

22:17 [Pub][ePrint]

In this paper, we present universal forgery and key recovery attacks on the most popular hash-based MAC constructions, e.g., HMAC and NMAC, instantiated with an AES-like hash function Whirlpool. These attacks work with Whirlpool reduced to 6 out of 10 rounds in single-key setting. To the best of our knowledge, this is the first result on original\'\' key recovery for HMAC (previous works only succeeded in recovering the equivalent keys). Interestingly, the number of attacked rounds is comparable with that for collision and preimage attacks on Whirlpool hash function itself. Lastly, we present a distinguishing-H attack against the full HMAC- and NMAC-Whirlpool.

22:17 [Pub][ePrint]

Insynd is a cryptographic scheme for secure and privacy-preserving one-way messaging. Insynd is ideally suited for sending personalised breach notifications to end-users, enabling services to provide positive evidence to a third party that they have complied with their obligations (and conversely, for end-users to prove that the notification was not timely). Insynd provides i) secrecy of messages, ii) message integrity and authenticity, iii) protection against recipient profiling, and iv) publicly verifiable proofs of who sent what message to which recipient at what particular time. Our scheme is built on an authenticated data structure, named Balloon, enabling the safe outsourcing of storage of messages to an untrusted server (such as commodity cloud services). The author of messages is in the forward-security model. Insynd uses modern cryptographic primitives, making it also a suitable secure logging system or evidence store, despite the use of \"slow\" public-key cryptography. Our prototype implementation shows improved performance over related work and competitive performance for more data-intensive settings like secure logging.

22:17 [Pub][ePrint]

A 25-gigabyte \"point obfuscation\" challenge \"using security parameter 60\" was announced at the Crypto 2015 rump session; \"point obfuscation\" is another name for password hashing. This paper shows that the particular matrix-multiplication hash function used in the challenge is much less secure than previous password-hashing functions are believed to be. This paper\'s attack algorithm broke the challenge in just 19 minutes using a cluster of 21 PCs.

22:17 [Pub][ePrint]

The calculation of the Tate pairing on ordinary curves involves two major steps: the Miller Loop (ML) followed by the Final Exponentiation (FE). The first step for achieving a full pairing inversion would be to invert this FE, which in itself is a mathematically difficult problem. To our best knowledge, most fault attack schemes proposed against pairing algorithms have mainly focussed on the ML. They solved, if at all, the inversion of the FE in some special easy\' cases or even showed that the complexity of the FE is an intrinsic countermeasure against a successful full fault attack on the Tate pairing. In this paper, we present a fault attack on the FE whereby the inversion of the final exponentiation becomes feasible using $3$ independent faults.

22:17 [Pub][ePrint]

Functional encryption (FE) enables fine-grained access control of encrypted data while promising simplified key management. In the past few years substantial progress has been made on functional encryption and a weaker variant called predicate encryption. Unfortunately, fundamental impossibility results have been demonstrated for constructing FE schemes for general functions satisfying a simulation-based definition of security.

We show how to use \\emph{hardware tokens} to overcome these impossibility results. In our envisioned scenario, an authority gives a hardware token and some cryptographic information to each authorized user; the user combines these to decrypt received ciphertexts. Our schemes rely on \\emph{stateless} tokens that are \\emph{identical} for all users. (Requiring a different token for each user trivializes the problem, and would be a barrier to practical deployment.) The tokens can implement relatively `lightweight\'\' computation relative to the functions supported by the scheme.

Our token-based approach can be extended to support hierarchal functional encryption, function privacy, and more.

22:17 [Pub][ePrint]

We study the question of protecting arithmetic circuits against additive attacks, which can add an arbitrary fixed value to each wire in the circuit.

This extends the notion of algebraic manipulation detection (AMD) codes, which protect information against additive attacks, to that of AMD circuits which protect computation.

We present a construction of such AMD circuits: any arithmetic circuit $C$ over a finite field $F$ can be converted into a functionally-equivalent randomized arithmetic circuit $\\widehat{C}$ of size $O(|C|)$ that is fault-tolerant in the following sense. For any additive attack on the wires of $\\widehat{C}$, its effect on the output of $\\widehat{C}$ can be simulated, up to $O(|C|/|F|)$ statistical distance, by an additive attack on just the input and output.

Given a small tamper-proof encoder/decoder for AMD codes, the input and output can be protected as well.

We also give an alternative construction, applicable to small fields (for example, to protect Boolean circuits against wire-toggling attacks). It uses a small tamper-proof decoder to ensure that, except with negligible failure probability, either the output is correct or tampering is detected.

Our study of AMD circuits is motivated by simplifying and improving protocols for secure multiparty computation (MPC). Typically, securing MPC protocols against active adversaries is much more difficult than securing them against passive adversaries.

We observe that in simple MPC protocols that were designed to protect circuit evaluation only against passive adversaries, the effect of any active adversary corresponds precisely to an additive attack on the original circuit\'s wires. Thus, to securely evaluate a circuit $C$ in the presence of active adversaries, it suffices to apply the passive-secure protocol to $\\widehat{C}$. We use this methodology to simplify feasibility results and attain efficiency improvements in several standard MPC models.

22:17 [Pub][ePrint]

Several new services incentivize clients to compete in

solving large computation tasks in exchange for financial rewards.

This model of competitive distributed computation enables every

user connected to the Internet to participate in a game in which

he splits his computation power among a set of competing pools

-- the game is called a computation power splitting game. We

formally model this game and show its utility in analyzing the

security of pool protocols that dictate how financial rewards are

shared among the members of a pool.

As a case study, we analyze the Bitcoin cryptocurrency

which attracts computing power roughly equivalent to billions

of desktop machines, over 70% of which is organized into public

pools. We show that existing pool reward sharing protocols

are insecure in our game-theoretic analysis, when considering

a single attack strategy called the \"block withholding attack\".

This attack is a topic of debate, initially thought to be ill-

incentivized in today\'s pool protocols: i.e., causing a net loss

to the attacker, and later argued to be always profitable. Our

analysis shows that the attack is always well-incentivized in the

long-run, but may not be so for a short duration. This implies that

existing pool protocols are insecure, and if the attack is conducted

systematically, Bitcoin pools could lose millions of dollars worth

in months. The equilibrium state is a mixed strategy--that is--in

equilibrium all clients are incentivized to probabilistically attack

to maximize their payoffs rather than participate honestly. As

a result, the overall capacity of the Bitcoin network is under-

utilized.