International Association
for Cryptologic Research

Last week, IACR ePrint archive posted two fully homomorphic encryption schemes

without bootstrapping. In this note, we show that these schemes are trivially insecure.

Submission: 30 June 2015
Notification: 31 August 2015
From November 9 to November 12
Location: Florianopolis - SC, Brazil
More Information: http://sbseg2015.univali.br/en

The Number Field Sieve (NFS) algorithm is the best known method to

compute discrete logarithms (DL) in large characteristic finite fields

$\\FF_{p^n}$, with $p$ large and $n \\geq 1$ small. This algorithm

comprises four steps: polynomial selection, relation collection,

linear algebra and finally, individual logarithm computation. The

first step outputs two numbers fields equipped with a map to

$\\FF_{p^n}$. After the relation collection and linear algebra

phases, the (virtual) logarithm of a subset of elements in each number

field is known. The fourth step computes a preimage in one number

field of the target element in $\\FF_{p^n}$. If one can write the

target preimage as a product of elements of known (virtual) logarithm,

then one can deduce the discrete logarithm of the target.

The traditional approach for the individual logarithm step can be

extremely slow, and it is too slow especially for

$n$ greater than 3. Its asymptotic complexity is $L_Q[1/3, c]$ with $c

\\geq 1.44$. We present a new preimage computation that provides a

dramatic improvement for individual logarithm computations for small

$n$, both in practice and in asymptotic running-time: we have

$L_Q[1/3, c]$ with $c = 1.14$ for $n=2,4$, $c = 1.26$ for $n=3,6$ and

$c = 1.34$ for $n=5$. Our method generalizes to any $n$; in particular

$c < 1.44$ for the two state-of-the-art variants of NFS for extension

fields.

Time-lock puzzles, introduced by May, Rivest, Shamir and Wagner, is a mechanism for sending messages ``to the future\'\'. A sender

can quickly generate a puzzle with a solution $s$ that remains hidden until a moderately large amount of time $t$ has elapsed. The solution $s$ should be hidden from any adversary that runs in time significantly less than $t$, including resourceful parallel adversaries with polynomially many processors.

While the notion of time-lock puzzles has been around for 22 years, there has only been a *single* candidate proposed. Fifteen years ago, Rivest, Shamir and Wagner suggested a beautiful candidate time-lock puzzle based on the assumption that exponentiation modulo an RSA integer is an ``inherently sequential\'\' computation.

We show that various flavors of {\\em randomized encodings} give rise to time-lock puzzles of varying strengths, whose security can be shown assuming *the existence* of non-parallelizing languages, which are languages that require circuits of depth at least $t$ to decide, in the worst-case. The existence of such languages is necessary for the existence of time-lock puzzles.

We instantiate the construction with different randomized

encodings from the literature, where increasingly better efficiency is obtained based on increasingly stronger cryptographic assumptions, ranging from one-way functions to indistinguishability obfuscation. We also observe that time-lock puzzles imply one-way functions, and thus the reliance on some cryptographic assumption is necessary.

Finally, generalizing the above, we construct other types of puzzles such as *proofs of work* from randomized encodings and a

suitable worst-case hardness assumption (that is necessary for such puzzles to exist).

At CRYPTO 2012, Knellwolf and Khovratovich presented a differential formulation of advanced meet-in-the-middle techniques for preimage attacks on hash functions. They demonstrated the usefulness of their approach by significantly improving the previously best known attacks on SHA-1 from CRYPTO~2009, increasing the number of attacked rounds from a 48-round one-block pseudo-preimage without padding and a 48-round two-block preimage without padding to a 57-round one-block preimage without padding and a 57-round two-block preimage with padding, out of 80 rounds for the full function.

In this work, we exploit further the differential view of meet-in-the-middle techniques and generalize it to higher-order differentials. Despite being an important technique dating from the mid-90\'s, this is the first time higher-order differentials have been applied to meet-in-the-middle preimages. We show that doing so may lead to significant improvements to preimage attacks on hash functions with a simple linear message expansion. We extend the number of attacked rounds on SHA-1 to give a 62-round one-block preimage without padding, a 56-round one-block preimage with padding, and a

62-round two-block preimage with padding. We also apply our framework to the more recent SHA-3 finalist BLAKE and its newer variant BLAKE2, and give an attack for a 2.75-round preimage with padding, and a 7.5-round pseudo-preimage on the compression function.

The ASASA construction is a new design scheme introduced at ASIACRYPT 2014 by Biruykov, Bouillaguet and Khovratovich. Its versatility was illustrated by building two public-key encryption schemes, a secret-key scheme, as well as super S-box subcomponents of a white-box scheme. However one of the two public-key cryptosystems was recently broken at CRYPTO 2015 by Gilbert, Plût and Treger.

As our main contribution, we propose a new algebraic key-recovery attack able to break at once the secret-key scheme as well as the remaining public-key scheme, in time complexity 2^63 and 2^39 respectively (the security parameter is 128 bits in both cases).

Furthermore, we present a second attack of independent interest on the same public-key scheme, which heuristically reduces the problem of breaking the scheme to an LPN instance with tractable parameters. This allows key recovery in time complexity 2^56.

Finally, as a side result, we outline a very efficient heuristic attack on the white-box scheme, which breaks instances claiming 64 bits of security under one minute on a desktop computer.

Submission: 15 April 2016
Notification: 1 August 2016
From December 1 to December 2
Location: Kuala Lumpur, Malaysia
More Information: https://foe.mmu.edu.my/mycrypt2016/

In this paper we detail techniques that can be used to analyze and attack an AES implementation on an FPGA from the primary (i.e., external) side of a switched-mode power supply. Our attack only requires measurements of the duty cycle of the power supply, and then increases the signal-to-noise ratio (SNR) though averaging, deconvolution and wavelet based detrending. The result is an exploitable source of leakage that allows a secret key to be determined from low-frequency power measurements. The techniques and procedures provide a general approach to performing differential power analysis (DPA) from a single point of information for any single hypothesized intermediate value, suggesting their potential for improving other types of side-channel analysis as well.

The Security Lab at Swedish Institute of Computer Science (SICS) in Lund and Stockholm is looking for talent post doc researchers in computer and network security. The positions are for 18 months with a monthly salary of 35.000 SEK and the positions can be filled in either Lund or Stockholm. Starting dates are flexible but not later than October 1, 2015. The suitable candidates will work in our EU H2020 financed research projects devoted to 5G security with focus on identity and key management, SDN security as well as in security for Platform as a Service (PaaS) systems (See also the following project page: https://sites.google.com/site/paaswordeu/)

The security Lab at SICS was established in 2009. Since then it has grown from 1 to 12 people. The research is directed toward secure systems design in close co-operation with above leading Swedish companies in the IT and telecommunications businesses as well as Swedish universities such as Royal Institute of Technology in Stockholm and Lund University. The group is active in the areas of embedded systems security, cloud security, access control and communications security. The security lab at SICS consists for the moment of 6 senior researchers (PhD), 3 PhD students and 3 junior researchers with MSc degrees in computer science.

Applicants interested in the positions should provide the following information in pdf format with the application:

- Application letter

- CV

- Transcript of grades

- Publications list

- 3-5 selected full text publications

Submission: 15 April 2016
Notification: 1 August 2016
From December 1 to December 2
Location: Kuala Lumpur, Malaysia
More Information: https://foe.mmu.edu.my/mycrypt2016/

Submission: 15 April 2016
Notification: 1 August 2016
From December 1 to December 2
Location: Kuala Lumpur, Malaysia
More Information: https://foe.mmu.edu.my/mycrypt2016/

The security of pairing-based crypto-systems relies on the difficulty to compute discrete logarithms in finite fields GF(p^n) where n is a small integer larger than 1. The state-of-art algorithm is the number field sieve (NFS) together with its many variants. When p has a special form (SNFS), as in many pairings constructions, NFS has a faster variant due to Joux and Pierrot. We present a new NFS variant for SNFS computations, which is better for some cryptographically relevant cases, according to a precise comparison of norm sizes. The new algorithm is an adaptation of Schirokauer\'s variant of NFS based on tower extensions, for which we give a middlebrow presentation.

The prevailing approach for building masked algorithms that can resist higher-order differential power analysis is to develop gadgets, that is, masked gates used as atomic blocks, that securely implement basic operations from the original algorithm, and then to compose these gadgets, introducing refresh operations at strategic places to guarantee that the complete circuit is protected. These compositional principles are embedded in so-called masking transformations, which are used as heuristics to achieve secure composition. Unfortunately, these transformations are seldom proved secure rigorously, and in fact, sometimes yield algorithms that are not secure against higher-order attacks. In this paper, we define a notion of strong simulatability that naturally supports compositional principles. Although this notion is stronger than the notion of simulatability (or perfect simulation) from previous works, we show that it is satisfied by several gadgets from the literature, including the mask refreshing gadget from Duc, Dziembowski and Faust (Eurocrypt 2014), the secure multiplication gadget from Rivain and Prouff (CHES 2010) and the secure multiplication gadget between dependent inputs from Coron et al. (FSE 2013). Then, we exploit a tight connection between strong simulatability and probabilistic information flow policies to define a (fine-grained, incremental) type system that checks (strong) simulatability of algorithms. We use the type system to validate a novel and automated transformation that outputs masked algorithms at arbitrary orders. Finally, we measure the performance of masked algorithms of AES, Keccak-f, Simon, and Speck generated by our transformation. The results are encouraging: for AES, masking at order 5, 20, and 100 respectively incur slowdowns of 100x, 750x, and x1500 w.r.t. the unmasked implementation given as input to our tool.

We consider the problem of recovering the internal specification of a general SP-network consisting of three linear layers (A) interleaved with two Sbox layers (S) (denoted by ASASA for short), given only black-box access to the scheme. The decomposition of such general ASASA schemes was first considered at ASIACRYPT 2014 by Biryukov et al. which used the alleged difficulty of this problem to propose several concrete block cipher designs as candidates for white-box cryptography.

In this paper, we present several attacks on general ASASA schemes that significantly outperform the analysis of Biryukov et al. As a result, we are able to break all the proposed concrete ASASA constructions with practical complexity. For example, we can decompose an ASASA structure that was supposed to provide $64$-bit security in roughly $2^{28}$ steps, and break the scheme that supposedly provides $128$-bit security in about $2^{41}$ time. Whenever possible, our findings are backed up with experimental verifications.

Differential Fault Attack (DFA) has received serious attention in cryptographic literature and very recently

such attacks have been mounted against several popular stream ciphers for example Grain v1, MICKEY 2.0

and Trivium, that are parts of the eStream hardware profile. The basic idea of the fault attacks consider

injection of faults and the most general set-up should consider faults at random location and random time.

Then one should identify the exact location and the exact timing of the fault (as well as multi bit faults) with the help of fault signatures.

In this paper we consider this most general set-up and solve the problem of fault attack under a general framework,

where probabilistic signatures are exploited. Our ideas subsume all the existing DFAs against the Grain family,

MICKEY 2.0 and Trivium. In the process we provide improved fault attacks for all the versions of Grain family and also

for MICKEY 2.0 (the attacks against Trivium are already quite optimal and thus there is not much scope to improve).

Our generalized method can also take care of the cases where certain parts of the keystream bits are missing

for authentication purpose. In particular, we show that the unsolved problem of identifying the faults

in random time for Grain 128a can be solved in this manner. Our techniques can easily be applied to mount fault

attack on any stream cipher of similar kind.

An alleged theorem of Neven, Smart and Warinschi (NSW) about the

security of Schnorr signatures seems to have a flaw described in

this report.

Schnorr signatures require representation of an element in a

discrete logarithm group as a hashable bit string. This report

describes a defective bit string representation of elliptic curve

points. Schnorr signatures are insecure when used with this

defective representation. Nevertheless, the defective

representation meets all the conditions of the NSW theorem.

Of course, a natural representation of an elliptic curve group

element would not suffer from this major defect. So, the NSW

theorem can probably be fixed.

Plaintext is mixed with AI-generated dis-information which binds the cryptanalyst to an irreducible set of mutually exclusive plausible plaintext candidates.

As impractical as Vernam \"One Time Pad\" cipher has been, it\'s security strategy: equivocation is fundamentally superior to the prevailing strategy: intractability. Intractability erodes, equivocation endures. Alas, Vernam was an overkill. Equivocation works even if only a few plaintext candidates are left as an irreducible set, which is what Equivoe-T offers.

The AI engine builds decoys off the plaintext such that each decoy has a counter-meaning, or at least an off-meaning per the guarded plaintext, while claiming at least threshold plausibility to \"pump\" entropy into the irreducible field of plaintext candidates.

Equivoe-T uses a complete transposition algorithm that guarantees the existence of a key that matches any two arbitrarily selected permutations of the n transposed elements. Therefore every decoy qualifies as a plaintext. The transposed elements may be words, letters, a mix, or otherwise. n can be selected to add intractability to the built-in equivocation since the key space grows fast (|Ktransposition| = n!).

Side channel collision attacks are a powerful method to exploit side channel leakage. Otherwise than a few exceptions, collision attacks usually combine leakage from distinct points in time, making them inherently bivariate. This work introduces the notion of near collisions to exploit the fact that values depending on the same sub-key can have similar while not identical leakage. We show how such knowledge can be exploited to mount a key recovery attack. The presented approach has several desirable features when compared to other state-of-the-art collision attacks:

Near collision attacks are truly univariate. They have low requirements on the leakage functions, since they work well for leakages that are linear in the bits of the targeted intermediate state. They are applicable in the presence of masking countermeasures if there exist distinguishable leakages, as in the case of leakage squeezing.

Results are backed up by a broad range of simulations for unprotected and masked implementations, as well as an analysis of the measurement set provided by DPA Contest v4.

The Norwegian government ran trials of internet remote voting during the 2011 municipal elections and the 2013 parliamentary elections. From a simplified version of the voting protocol used there, the essential cryptographic operations of the voting protocol has been put together into a cryptosystem in which one can build the voting protocol on top of.

This paper proposes a new instantiation of the underlying cryp- tosystem, improving our confidence in the security of the cryptosys- tem. The new instantiation is mostly similar to a previously defined instantiation, but allows parts of the security proof to be significantly improved.

We introduce and study the iterated random permutation problem, which asks how hard it is to distinguish, in a black-box way, the r-th power of a random permutation from a uniformly random permutation of a set of size N. We show that this requires Omega(N) queries (even for a two-sided, adaptive adversary). As a direct application of this result, we show that cascading a block cipher with the same key cannot degrade its security (as a pseudorandom permutation) more than negligibly.