International Association
for Cryptologic Research

In this article, we study the security of iterative hash-based MACs, such as HMAC or NMAC, with regards to universal forgery attacks. Leveraging recent advances in the analysis of functional graphs built from the iteration of HMAC or NMAC, we exhibit the very first generic universal forgery attack against hash-based MACs. In particular, our work implies that the universal forgery resistance of an n-bit output HMAC construction is not 2^n queries as long believed by the community. The techniques we introduce extend the previous functional graphs-based attacks that only took in account the cycle structure or the collision probability: we show that one can extract much more meaningful secret information by also analyzing the distance of a node from the cycle of its component in the functional graph.

We are interested in secure computation protocols in settings where the number of parties is huge and their data even larger. Assuming the existence of a single-use broadcast channel (per player), we demonstrate statistically secure computation protocols for computing (multiple) arbitrary dynamic RAM programs over parties\' inputs, handling (1/3-eps) fraction static corruptions, while preserving up to polylogarithmic factors the computation and memory complexities of the RAM program. Additionally, our protocol is load balanced and has polylogarithmic communication locality.

In a recent celebrated breakthrough, Garg et al. (FOCS 2013) gave the first candidate for so-called indistinguishability obfuscation (iO) thereby reviving the interest in obfuscation for a general purpose. Since then, iO has been used to advance numerous sub-areas of cryptography. While indistinguishability obfuscation is a general purpose obfuscation scheme, several obfuscators for specific functionalities have been considered. In particular, special attention has been given to the obfuscation of so-called \\emph{point functions} that return zero everywhere, except for a single point $\\alpha$. A strong variant is point obfuscation with auxiliary input (AIPO), which allows an adversary to learn some non-trivial auxiliary information about the obfuscated point $\\alpha$ (Goldwasser, Tauman-Kalai; FOCS, 2005).

Multi-bit point functions are a strengthening of point functions, where on $\\alpha$, the point function returns a string $\\beta$ instead of $1$. Multi-bit point functions with auxiliary input (MB-AIPO) have been constructed by Canetti and Bitansky (Crypto 2010) and have been used by Matsuda and Hanaoka (TCC 2014) to construct CCA-secure public-key encryption schemes and by and Bitansky and Paneth (TCC 2012) to construct three-round weak zero-knowledge protocols for NP.

In this paper we present both positive and negative results. We show that if indistinguishability obfuscation exists, then MB-AIPO does not. Towards this goal, we build on techniques by Brzuska, Farshim and Mittelbach (Crypto 2014) who use indistinguishability obfuscation as a means of attacking a large class of assumptions from the Universal Computational Extractor framework (Bellare et al; Crypto 2013). On the positive side we introduce a weak version of MB-AIPO which we deem to be outside the reach of our impossibility result. We prove that this weak version of MB-AIPO suffices to construct a public-key encryption scheme that is secure even if the adversary can learn an arbitrary leakage function of the secret key, as long as the secret key remains computationally hidden. Thereby, we strengthen a result by Canetti et al. (TCC 2010) that showed a similar connection in the symmetric-key setting.

In this paper we study the security of hash-based MAC algorithms (such as HMAC and NMAC) above the birthday bound. Up to the birthday bound, HMAC and NMAC are proven to be secure under reasonable assumptions on the hash function. On the other hand, if an $n$-bit MAC is built from a hash function with a $l$-bit state ($l \\ge n$), there is a well-known existential forgery attack with complexity $2^{l/2}$. However, the remaining security after $2^{l/2}$ computations is not well understood. In particular it is widely assumed that if the underlying hash function is sound, then a generic universal forgery attack should still require $2^{n}$ computations and some distinguishing (e.g. distinguishing-H but not distinguishing-R) and state-recovery attacks should still require $2^{l}$ (or $2^k$ if $k < l$) computations.

In this work, we show that above the birthday bound, hash-based MACs offer significantly less security than previously believed. Our main result is a generic distinguishing-H and state-recovery attack against hash-based MACs with a complexity of only $\\tilde O(2^{l/2})$. In addition, we show a key-recovery attack with complexity $\\tilde O(2^{3l/4})$ against HMAC used with a hash functions with an internal checksum, such as GOST. This surprising result shows that the use of a checksum might actually weaken a hash function when used in a MAC. We stress that our attacks are generic, and they are in fact more efficient than some previous attacks proposed on MACs instantiated with concrete hash functions.

We use techniques similar to the cycle-detection technique proposed by Peyrin et al. at Asiacrypt 2012 to attack HMAC in the related-key model. However, our attacks works in the single-key model for both HMAC and NMAC, and without restriction on the key size.

We present a symmetric-key predicate-only functional encryption system, SP-FE, which supports functionality for regular languages describe by deterministic finite automata. In SP-FE, a data owner can encrypt a string of symbols as encrypted symbols for matching. Later, the data owner can generate predicate tokens of the transitions in a deterministic finite automaton. The server with these tokens can decrypt a sequence of encrypted symbols correctly and transfer from one state to another accordingly. If the final state belongs to the set of accept states, the server takes assigned operations or returns the corresponding encrypted data. We have proven SP-FE preserves both plaintext privacy and predicate privacy through security analysis and security games. To achieve predicate privacy, we put bounds on the length of a string and the number of states of a DFA. Due to these restrictions, SP-FE can capture only finite languages. Finally, we present the performance analysis of SP-FE and mention possible future work.

This looks like a paper of "how to tranform secret key algorithm into public key one using obfuscation". Take AES-X, and obfuscate. From: 2014-02-06 05:46:14 (UTC)

This paper presents a new projective coordinate system and new explicit algorithms which together boost the speed of arithmetic in the divisor class group of genus 2 curves. The proposed formulas generalise the use of Jacobian coordinates on elliptic curves, and their application improves the speed of performing cryptographic scalar multiplications in Jacobians of genus 2 curves over prime fields by an approximate factor of 1.25x. For example, on a single core of an Intel Core i7-3770M (Ivy Bridge), we show that replacing the previous best formulas with our new set improves the cost of generic scalar multiplications from 243,000 to 195,000 cycles, and drops the cost of specialised GLV-style scalar multiplications from 166,000 to 129,000 cycles.

We propose Chaskey: a very efficient Message Authentication Code (MAC) algorithm for 32-bit microcontrollers. It is intended for applications that require 128-bit security, yet cannot implement standard MAC algorithms because of stringent requirements on speed, energy consumption, or code size. Chaskey is a permutation-based MAC algorithm that uses the Addition-Rotation-XOR (ARX) design methodology. We formally prove that Chaskey is secure in the standard model, based on the security of an underlying Even-Mansour block cipher. Chaskey is designed to perform well on a wide range of 32-bit microcontrollers. Our benchmarks show that on the ARM Cortex-M3/M4, our Chaskey implementation reaches a speed of 7.0 cycles/byte, compared to 89.4 cycles/byte for AES-128-CMAC. For the ARM Cortex-M0, our benchmark results give 16.9 cycles/byte and 136.5 cycles/byte for Chaskey and AES-128-CMAC respectively.

We present a new method for building pairs of HFE polynomials of high degree, such that the map constructed with such a pair is easy to invert. The inversion is accomplished using a low degree polynomial of Hamming weight three, which is derived from a special reduction via Hamming weight three polynomials produced by these two HFE polynomials. This allows us to build new candidates for multivariate trapdoor functions in which we use the pair of HFE polynomials to fabricate the core map. We performed the security analysis for the case where the base field is $GF(2)$ and showed that these new trapdoor functions have high degrees of regularity, and therefore they are secure against the direct algebraic attack. We also give theoretical arguments to show that these new trapdoor functions over $GF(2)$ are secure against the MinRank attack as well.

The modification of message that meets the sufficient conditions for

collision is found in the last step of differential attack proposed

by Wang et all. (2005) on MD4 hash algorithm. Here we show how this

attack phase, finding a collision starting from the list of

sufficient conditions for the collision, can be implemented using a

combination of two algorithms - evolutionary algorithm and hill

climbing. Hybridization of evolutionary algorithm and hill climbing

is a well-known technique for improving solutions, but it isn\'t

applied to this domain (at least by information that author has

collected).

In this work we introduce a large polynomial arithmetic library optimized for Nvidia GPUs to support fully homomorphic encryption schemes. To realize the large polynomial arithmetic library we convert the polynomial with large coefficients using the Chinese Remainder Theorem into many polynomials with small coefficients, and then carry out modular multiplications in the residue space using a custom developed discrete Fourier transform library. We further extend the library to support the homomorphic evaluation operations, i.e. addition, multiplication, and relinearization, in an NTRU based somewhat homomorphic encryption library. Finally, we put the library to use to evaluate homomorphic evaluation of two block ciphers: Prince and AES, which show 2.57 times and 7.6 times speedup, respectively, over an Intel Xeon software implementation.

Motivated by theoretical and practical interest, the challenging task of designing crypto- graphic protocols having only black-box access to primitives has generated various breakthroughs in the last decade. Despite such positive results, even though nowadays we know black-box constructions for secure two-party and multi-party computation even in constant rounds, there still are in Cryptography several constructions that critically require non-black-box use of primitives in order to securely realize some fundamental tasks. As such, the study of the gap between black-box and non-black-box constructions still includes major open questions.

In this work we make progress towards filling the above gap. We consider the case of black- box constructions for computations requiring that even the size of the input of a player remains hidden. We show how to commit to a string of arbitrary size and to prove statements over the bits of the string. Both the commitment and the proof are succinct, hide the input size and use standard primitives in a black-box way. We achieve such a result by giving a black-box construction of an extendable Merkle tree that relies on a novel use of the \"MPC in the head\" paradigm of Ishai et al. [STOC 2007].

We show the power of our new techniques by giving the first black-box constant-round public-coin zero knowledge argument for NP.

To achieve this result we use the non-black-box simulation technique introduced by Barak [FOCS 2001], the PCP of Proximity introduced by Ben-Sasson et al. [STOC 2004], together with a black-box public-coin witness indistinguishable universal argument that we construct along the way.

Additionally we show the first black-box construction of a generalization of zero-knowledge sets introduced by Micali et al. [FOCS 2003]. The generalization that we propose is a strengthening that requires both the size of the set and the size of the elements of the set to remain private.

Big data and its applications are attracting more and more research interests in recent years. As the new generation distributed computing platform, cloud computing is believed to be the most potent platform. With the data no longer under users\' direct control, data security in cloud computing is becoming one of the most obstacles of the proliferation of cloud. In order to improve service reliability and availability, storing multiple replicas along with original datasets is a common strategy for cloud service providers. Public data auditing schemes allow users to verify their outsourced data storage without having to retrieve the whole dataset. However, existing data auditing techniques suffers from efficiency and security problems. First, for dynamic datasets with multiple replicas, the communication overhead for update verification is very large, because verification for each update requires O(logn) communication complexity and update of all replicas. Second, to the best of our knowledge, there is no existing integrity verification schemes can provide public auditing and authentication of block indices at the same time. Without authentication of block indices, the server can build a valid proof based on data blocks other than the block client requested to verify. In order to address these problems, in this paper, we present a novel public auditing scheme named MuR-DPA. The new scheme incorporated a novel authenticated data structure based on the Merkle hash tree, which we name as MR-MHT. For support of full dynamic data updates, authentication of block indices and efficient verification of updates for multiple replicas at the same time, the level values of nodes in MR-MHT are generated in a top-down order, and all replica blocks for each data block are organized into a same replica sub-tree. Compared to existing integrity verification and public auditing schemes, theoretical analysis and experimental results show that the MuR-DPA scheme can not only incur much less communication overhead for both update and verification of datasets with multiple replicas, but also provide enhanced security against dishonest cloud service providers.

We revisit ``the randomized iterate\'\' technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) and refined by Haitner, Harnik and Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). We abstract out a technical lemma with connections to several recent work on cryptography with imperfect randomness, which provides an arguably simpler and more modular proof for the Haitner-Harnik-Reingold PRGs from regular OWFs.

We extend the approach to a more general construction of PRGs with seed length $O(n{\\log}n)$ from a broader class of OWFs. More specifically, consider an arbitrary one-way function $f$ whose range is divided into sets $\\Y_1$, $\\Y_2$, $\\ldots$, $\\Y_n$ where each $\\Y_i\\eqdef\\{y:2^{i-1}\\le|f^{-1}(y)|

A universal one-way hash function (UOWHF) is a compressing function for which finding a second preimage is infeasible. The seminal work of Rompel (STOC 1990) that one-way functions (OWFs) imply UOWHFs is one of the most important founding results of modern cryptography. The current best known UOWHF construction from any one-way function(on $n$-bit input) by Haitner et al. (Eurocrypt 2010) requires output and key length $\\tilO(n^7)$, which is far from practical.

On the other hand, special structured OWFs typically give rise to much more efficient (and almost practical) UOWHFs. Naor and Yung (STOC 1989) gave an optimal construction of UOWHFs of key and output lengths both linear in $n$ by making a single call to any one-way permutation. De Santis and Yung (Eurocrypt 1990), Barhum and Maurer (Latincrypt 2012), and Ames, Gennaro, and Venkitasubramaniam (Asiacrypt 2012) further extended the work to more generalized settings, namely, 1-to-1 and regular one-way functions. However, the best known constructions still require key length $O(n\\cdot\\log{n})$ even for 1-to-1 one-way functions, and need to make $O(\\omega(1 {\\cdot}\\log{n})$ calls to any known regular one-way functions, or even $\\tilO(n)$ adaptive calls if one wants linear output length at the same time.

In this paper, we first introduce a technical lemma about universal hashing with nice symmetry to the leftover hash lemma, which might be of independent interest. That is, if one applies universal hash function $h:\\bit{n}\\rightarrow\\bit{a+d}$ to any random variable $X$ of min-entropy $a$, then $h$ will be 1-to-1 on $X$ except for a $2^{-d}$ fraction. We also generalize the construction of Naor and Yung (that was optimal only for one-way permutations) to 1-to-1 and almost regular one-way functions, and significantly extend their analysis. The above yields the following results.

\\begin{itemize}

\\item For any 1-to-1 one-way function, we give an optimal construction of UOWHFs with key and output length $\\Theta(n)$ by making a single call to the underlying OWF.

\\item For any known-(almost-)regular one-way function with known hardness, we give another optimal construction of UOWHFs with key and output length $\\Theta(n)$ and a single call to the one-way function.

\\item For any known-(almost-)regular one-way function, we give a construction of UOWHFs with key and output length $O(\\omega(1){\\cdot}n)$ and by making $\\omega(1)$ non-adaptive calls to the one-way function.

\\end{itemize}

where the first two constructions enjoy optimal parameters simultaneously and the third one is nearly optimal up to any(efficiently computable) super-constant factor $\\omega(1)$, e.g., $\\log\\log\\log{n}$ or even less. Furthermore, the constructions enjoy optimal shrinkages by matching the upper bound of Gennaro et al. (SICOMP 2005).

Traditional cryptographic hash functions allow one to easily check whether the original plain-texts are equal or not, given a pair of hash values. Probabilistic hash functions extend this concept where given a probabilistic hash of a value and the value itself, one can efficiently check whether the hash corresponds to the given value. However, given distinct probabilistic hashes of the same value it is not possible to check whether they correspond to the same value. In this work we introduce a new cryptographic primitive called \\emph{relational hash} using which, given a pair of (relational) hash values, one can determine whether the original plain-texts were related or not. We formalize various natural security notions for the relational hash primitive - one-wayness, unforgeability and oracle simulatibility.

We develop a relational hash scheme for discovering linear relations among bit-vectors (elements of $\\FF_2^n$) and $\\FF_p$-vectors. Using these linear relational hash schemes we develop relational hashes for detecting proximity in terms of hamming distance. These proximity relational hashing scheme can be adapted to a privacy preserving biometric authentication scheme.

We also introduce the notion of \\emph{relational encryption}, which is a regular semantically secure public key encryption for any adversary which only has access to the public key. However, a semi-trusted entity can be given a relational key using which it can discover relations among ciphertexts, but still cannot decrypt and recover the plaintexts.

Proofs of storage (POR or PDP) is a cryptographic tool, which enables data owner or third party auditor to audit integrity of data stored remotely in a cloud storage server, without keeping a local copy of data or downloading data back during auditing. We observe that all existing publicly verifiable POS schemes suffer from a serious drawback: It is extremely slow to compute authentication tags for all data blocks, due to many expensive group exponentiation operations. Surprisingly, it is even much slower than typical network uploading speed, and becomes the bottleneck of the setup phase of the POS scheme. We propose a new variant formulation called \"Delegatable Proofs of Storage\". In this new relaxed formulation, we are able to construct POS schemes, which on one side is as efficient as private key POS schemes, and on the other side can support third party auditor and can switch auditors at any time, close to the functionalities of publicly verifiable POS schemes. Compared to traditional publicly verifiable POS schemes, we speed up the tag generation process by at least several hundred times, without sacrificing efficiency in any other aspect. Like many existing schemes, we can also speed up our tag generation process by N times using N CPU cores in parallel. We prove that our scheme is sound under Bilinear Strong Diffie-Hellman Assumption, and it is privacy preserving against auditor under Discrete Log Assumption. Both proofs are given in standard model.

Several recent short NIZK arguments are constructed in a modular way from a small number of basic arguments like the product argument or the shift argument. The main technical novelty of the current work is a significantly more efficient version of the product argument.

Based on this, we propose an adaptive NIZK range argument with almost optimal complexity: constant communication (in group elements), constant verifier\'s computational complexity (in cryptographic operations), and $\\Theta (n \\log n)$ [resp., $\\Theta (n)$] prover\'s computational complexity (in non-cryptographic [resp., cryptographic] operations). The latter can be compared to $n \\log^{\\omega (1)} n$ in the most efficient \\emph{published} short adaptive non-interactive range argument, or $\\Theta (n \\log^2 n)$ [resp., $\\Theta (n \\log n)$] that is achievable when following QAP-based framework from Eurocrypt 2013. Here, $n$ is the logarithm of the range length.

The new product argument can be used to construct efficient adaptive NIZK arguments for many other languages, including several that are $\\mathsf{NP}$-complete like $\\textsc{SubsetSum}$. Importantly, for all such languages, new adaptive arguments achieve better prover\'s computation than the QAP-based framework.

We show how the cofactorization step, a compute-intensive part of the relation collection phase of the number field sieve (NFS), can be farmed out to a graphics processing unit. Our implementation on a GTX 580 GPU, which is integrated with a state-of-the-art NFS implementation, can serve as a cryptanalytic co-processor for several Intel i7-3770K quad-core CPUs simultaneously. This allows those processors to focus on the memory-intensive sieving and results in more useful NFS-relations found in less time.

Department of Computing at University of Surrey is currently seeking to make an appointment at Lecturer (equiv. to Assistant Professor) or Senior Lecturer (equiv. to Associate Professor) level in Cyber Security to support the Department’s continued growth by complementing our existing research strengths and contributing to the research leadership within the Department, to play a leading role in the recently established interdisciplinary Surrey Centre for Cyber Security (SCCS) and to contribute to the new MSc Information Security programme.

Applications are welcome particularly in the areas of Software Security, Web and Network Security, System Security, Applied Cryptography and Protocols, Privacy and Data Protection, Multimedia Security, Digital Forensics, and Human-Centred Security.

The Department is research-led with around 70 RAs and PhD students, and is attracting growing research support from funding bodies such as the UK Research Councils, UK Technology Strategy Board (TSB), the EU-IST, and also private foundations e.g. The Leverhulme Trust. Major IT, telecommunication, defence and security organisations are sponsoring research in the Department.

Applicants at the Lecturer level should have a relevant PhD, a developing track record in publication with demonstrable high potential in high-quality research and teaching. Applicants at the Senior Lecturer level will have an international research profile, a significant track record of high-quality publications in leading journals and conference proceedings, and experience in a leadership or development role in high quality teaching. A record in attracting research funding would be an advantage.

Closing date for applications is 30 June 2014. The post is to start in September 2014 or as soon as possible thereafter.