Skip to main content
main-content

Über dieses Buch

This book constitutes the refereed proceedings of the 12th International Conference on Applied Cryptography and Network Security, ACNS 2014, held in Lausanne, Switzerland, in June 2014. The 33 revised full papers included in this volume were carefully reviewed and selected from 147 submissions. They are organized in topical sections on key exchange; primitive construction; attacks (public-key cryptography); hashing; cryptanalysis and attacks (symmetric cryptography); network security; signatures; system security; and secure computation.

Inhaltsverzeichnis

Frontmatter

Key Exchange

New Modular Compilers for Authenticated Key Exchange

We present two new compilers that generically turn passively secure key exchange protocols (

KE

) into authenticated key exchange protocols (

AKE

) where security also holds in the presence of active adversaries. Security is shown in a very strong security model where the adversary is also allowed to i) reveal state information of the protocol participants and ii) launch theoretically and practically important PKI-related attacks that model important classes of unknown-key share attacks. Although the security model is much stronger, our compilers are more efficient than previous results with respect to many important metrics like the additional number of protocol messages and moves, the additional computational resources required by the compiler or the number of additional primitives applied. Moreover, we advertise a mechanism for implicit key confirmation. From a practical point of view, the solution is simple and efficient enough for authenticated key exchange. In contrast to previous results, another interesting aspect that we do not require that key computed by the key exchange protocol is handed over to the compiler what helps to avoid additional and costly modifications of existing

KE

-based systems.

Yong Li, Sven Schäge, Zheng Yang, Christoph Bader, Jörg Schwenk

Password-Based Authenticated Key Exchange without Centralized Trusted Setup

Almost all existing password-based authenticated key exchange (PAKE) schemes achieve concurrent security in the standard model by relying on the common reference string (CRS) model. A drawback of the CRS model is to require a centralized trusted authority in the setup phase; thus, passwords of parties may be revealed if the authority ill-uses trapdoor information of the CRS. There are a few secure PAKE schemes in the plain model, but, these are not achievable in a constant round (i.e., containing a linear number of rounds). In this paper, we discuss how to relax the setup assumption for (constant round) PAKE schemes. We focus on the multi-string (MS) model that allows a number of authorities (including malicious one) to provide some reference strings independently. The MS model is a more relaxed setup assumption than the CRS model because we do not trust any single authority (i.e., just assuming that a majority of authorities honestly generate their reference strings). Though the MS model is slightly restrictive than the plain model, it is very reasonable assumption because it is very easy to implement. We construct a (concurrently secure) three-move PAKE scheme in the MS model (justly without random oracles) based on the Groce-Katz PAKE scheme. The main ingredient of our scheme is the multi-string simulation-extractable non-interactive zero-knowledge proof that provides both the simulation-extractability and the extraction zero-knowledge property even if minority authorities are malicious. This work can be seen as a milestone toward constant round PAKE schemes in the plain model.

Kazuki Yoneyama

A Linear Algebra Attack to Group-Ring-Based Key Exchange Protocols

In this paper we analyze the Habeeb-Kahrobaei-Koupparis-Shpilrain (HKKS) key exchange protocol which uses semidirect products of groups as a platform. We show that the particular instance of the protocol suggested in their paper can be broken via a simple linear algebra attack.

M. Kreuzer, A. D. Myasnikov, A. Ushakov

Primitive Construction

Improved Constructions of PRFs Secure Against Related-Key Attacks

Building cryptographic primitives that are secure against related-key attacks (RKAs) is a well-studied problem by practitioners and theoreticians alike. Practical implementations of block ciphers take into account RKA security to mitigate fault injection attacks. The theoretical study of RKA security was initiated by Bellare and Kohno (Eurocrypt ’03). In Crypto 2010, Bellare and Cash introduce a framework for building RKA-secure pseudorandom functions (PRFs) and use this framework to construct RKA-secure PRFs based on the decision linear and DDH assumptions.

We build RKA-secure PRFs by working with the Bellare-Cash framework and the LWE- and DLIN-based PRFs recently constructed by Boneh, Lewi, Montgomery, and Raghunathan (Crypto ’13). As a result, we achieve the first RKA-secure PRFs from lattices. In addition, we note that our DLIN-based PRF (based on multilinear maps) is the first RKA-secure PRF for affine classes under the DLIN assumption, and the first RKA-secure PRF against a large class of polynomial functions under a natural generalization of the DLIN assumption. Previously, RKA security for higher-level primitives (such as signatures and IBEs) were studied in Bellare, Paterson, and Thomson (Asiacrypt ’12) for affine and polynomial classes, but the question of RKA-secure PRFs for such classes remained open.

Although our RKA-secure LWE-based PRF only applies to a restricted linear class, we show that by weakening the notion of RKA security, we can handle a significantly larger class of affine functions. Finally, the results of Bellare, Cash, and Miller (Asiacrypt ’11) show that all of our RKA-secure PRFs can be used as building blocks for a wide variety of public-key primitives.

Kevin Lewi, Hart Montgomery, Ananth Raghunathan

Verifiable Multi-server Private Information Retrieval

Private information retrieval (PIR) allows a client to retrieve any block

x

i

from a database

x

 = 

x

1

 ⋯ 

x

n

(stored on a server) such that

i

remains hidden from the server. PIR schemes with unconditional privacy and sublinear (in

n

) communication complexity can be constructed assuming multiple honest-but-curious servers. This assumption however cannot be guaranteed in many real life scenarios such as using cloud servers. There are also extra properties such as efficient update of the database. In this paper, we consider a verifiable multi-server PIR (VPIR) model where the servers may be malicious and provide fraudulent answers. We construct an unconditionally

t

-private and computationally secure

k

-server VPIR scheme with communication complexity comparable to the best

t

-private

k

-server PIR scheme in the honest-but-curious server model. Our scheme supports efficient update of the database, identification of the cheating servers, tolerance of slightly corrupted answers, and multiple database outsourcing.

Liang Feng Zhang, Reihaneh Safavi-Naini

Certified Bitcoins

Bitcoin is a peer-to-peer (p2p) electronic cash system that uses a distributed timestamp service to record transactions in a public ledger (called the Blockchain). A critical component of Bitcoin’s success is the decentralized nature of its architecture, which does not require or even support the establishment of trusted authorities. Yet the absence of certification creates obstacles to its wider acceptance in e-commerce and official uses. We propose a certification system for Bitcoin that offers:

a

) an opt-in guarantee to send and receive bitcoins only to/ from certified users;

b

) control of creation of bitcoins addresses (certified users) by trusted authorities. Our proposal may encourage the adoption of Bitcoin in different scenarios that require an officially recognized currency, such as tax payments—often an integral part of e-commerce transactions.

Giuseppe Ateniese, Antonio Faonio, Bernardo Magri, Breno de Medeiros

Leakage Resilient Proofs of Ownership in Cloud Storage, Revisited

Client-side deduplication is a very effective mechanism to reduce both storage and communication cost in cloud storage service. Halevi

et al.

(CCS ’11) discovered security vulnerability in existing implementation of client-side deduplication and proposed a cryptographic primitive called “proofs of ownership” (PoW) as a countermeasure. In a proof of ownership scheme, any owner of the same file can prove to the cloud storage server that he/she owns that file in an efficient and secure manner, even if a bounded amount of any efficiently extractable information of that file has been leaked. We revisit Halevi

et al.

’s formulation of PoW and significantly improve the understanding and construction of PoW. Our contribution is twofold: Firstly, we propose a generic and conceptually simple approach to construct

Privacy-Preserving

Proofs of Ownership scheme, by leveraging on well-known primitives (i.e. Randomness Extractor and Proofs of Retrievability) and technique (i.e. sample-then-extract). Our approach can be roughly described as

Privacy-Preserving PoW = Randomness Extractor

+

Proofs of Retrievability

. Secondly, in order to provide a better instantiation of Privacy-Preserving-PoW, we propose a novel design of randomness extractor with large output size, which improves the state of art by reducing both the random seed length and entropy loss (i.e. the difference between the entropy of input and output) simultaneously.

Jia Xu, Jianying Zhou

Private Message Transmission Using Disjoint Paths

We consider private message transmission (PMT) between two communicants, Alice and Bob, in the presence of an eavesdropper, Eve. Alice and Bob have no shared keys and Eve is computationally unbounded. There is a total of

n

communicating paths, but not all may be simultaneously accessible to the parties. We let

t

a

,

t

b

, and

t

e

denote the number of paths that are accessible to Alice, Bob and Eve respectively. We allow the parties to change their accessed paths at certain points in time during the PMT protocol. We study perfect (P)-PMT protocol families that guarantee absolute privacy and reliability of message transmission. For the sake of transmission rate improvement, we also investigate asymptotically-perfect (AP)-PMT protocol families that provide negligible error and leakage and behave the same as P-PMT families when message length tends to infinity.

We derive the necessary and sufficient conditions under which P-PMT and AP-PMT are possible and introduce explicit PMT schemes. Our results show AP-PMT protocols attain much higher information rates than P-PMT ones. Interestingly, AP-PMT may be possible even in poor conditions where

t

a

 = 

t

b

 = 1 and

t

e

 = 

n

 − 1. We study applications of our results to private communication over the real-life scenarios of multiple-frequency links and multiple-route networks. We show practical examples of such scenarios that can be abstracted by the multipath setting: Our results prove the possibility of keyless information-theoretic private message transmission at rates 17% and 20% for the two example scenarios, respectively. We discuss open question and future work.

Hadi Ahmadi, Reihaneh Safavi-Naini

Attacks (Public-Key Cryptography)

Partial Key Exposure Attacks on Takagi’s Variant of RSA

We present several attacks on a variant of RSA due to Takagi when different parts of the private exponent are known to an attacker. We consider three cases when the exposed bits are the most significant bits, the least significant bits and the middle bits of the private exponent respectively. Our approaches are based on Coppersmith’s method for finding small roots of modular polynomial equations. Our results extend the results of partial key exposure attacks on RSA of Ernst, Jochemsz, May and Weger (EUROCRYPT 2005) for moduli from

N

 = 

pq

to

N

 = 

p

r

q

(

r

 ≥ 2).

Zhangjie Huang, Lei Hu, Jun Xu, Liqiang Peng, Yonghong Xie

New Partial Key Exposure Attacks on CRT-RSA with Large Public Exponents

In Crypto’03, Blömer and May provided several partial key exposure attacks on CRT-RSA. In their attacks, they suppose that an attacker can either succeed to obtain the most significant bits (MSBs) or the least significant bits (LSBs) of

d

p

 = 

d

mod (

p

 − 1) in consecutive order. For the case of known LSBs of

d

p

, their algorithm is polynomial-time only for small public exponents

e

(i.e.

e

 = poly(log

N

)). However, in some practical applications, we prefer to use large

e

(Like

e

 ≈ 

d

p

, to let the public and private operations with the same computational effort). In this paper, we propose some lattice-based attacks for this extended setting. For known LSBs case, we introduce two approaches that work up to

$e < N^{{3}\over{8}}$

. Similar results (though not as strong) are obtained for MSBs case. We also provide detailed experimental results to justify our claims.

Yao Lu, Rui Zhang, Dongdai Lin

Bit-Flip Faults on Elliptic Curve Base Fields, Revisited

As part of their investigation of fault attacks on elliptic curve cryptosystems, Ciet and Joye showed, back in 2003, that perturbing the value representing the cardinality of the base field in a physical implementation of ECC could result in a partial key recovery. They had to assume, however, that the perturbed computation would “succeed” in some sense, and that is rather unlikely to happen in practice.

In this paper, we extend their analysis and show that, in a somewhat stronger fault model, full key recovery is possible with a single fault. For example, our fault attack typically reduces 256-bit ECDLP to solving discrete logarithm problems in a few random elliptic curves over fields of less than 60 bits, which typically takes a matter of seconds. More generally, the asymptotic complexity of ECDLP becomes heuristically subexponential under our fault attack.

Our attack also extends to a very efficient full key recovery attack on ECDSA with two faulty signatures.

Taechan Kim, Mehdi Tibouchi

Hashing

All-but-One Dual Projective Hashing and Its Applications

Recently, Wee (EUROCRYPT’12) introduced the notion of dual projective hashing as an extension of the Cramer-Shoup projective hashing, with a simple construction of lossy trapdoor functions, and a simple construction of deterministic encryption schemes which is chosen-plaintext-attack secure with respect to hard-to-invert auxiliary input. In this work, we further extend it to the all-but-one setting by introducing the notion of all-but-one dual projective hashing.

We provide a simple construction of all-but-one lossy trapdoor functions. Our construction encompasses many known constructions of all-but-one lossy trapdoor functions, as presented by Peikert and Waters (STOC’08), and Freeman et al. (JoC’13). Particularly, we present a new construction of all-but-one lossy trapdoor functions based on the DLIN assumption, which can be viewed as an extension of Freeman et al.’s DDH-based construction to the DLIN setting, and therefore solves an open problem left by Freeman et al.

We also provide a general construction of chosen-ciphertext-attack (CCA) secure deterministic encryption schemes in the standard model, under an additional assumption about the projective map. This extends the general approach of designing CCA secure deterministic encryption schemes by Boldyreva, Fehr and O’Neill (CRYPTO’08). In addition, we present a new construction of CCA secure deterministic encryption schemes based on the DLIN assumption.

Zongyang Zhang, Yu Chen, Sherman S. M. Chow, Goichiro Hanaoka, Zhenfu Cao, Yunlei Zhao

Distributed Smooth Projective Hashing and Its Application to Two-Server Password Authenticated Key Exchange

Smooth projective hash functions have been used as building block for various cryptographic applications, in particular for password-based authentication.

In this work we propose the extended concept of

distributed

smooth projective hash functions where the computation of the hash value is distributed across

n

parties and show how to instantiate the underlying approach for languages consisting of Cramer-Shoup ciphertexts.

As an application of distributed smooth projective hashing we build a new framework for the design of two-server password authenticated key exchange protocols, which we believe can help to “explain” the design of earlier two-server password authenticated key exchange protocols.

Franziskus Kiefer, Mark Manulis

Sakura: A Flexible Coding for Tree Hashing

We propose a flexible, fairly general, coding for tree hash modes. The coding does not define a tree hash mode, but instead specifies a way to format the message blocks and chaining values into inputs to the underlying function for any topology, including sequential hashing. The main benefit is to avoid input clashes between different tree growing strategies, even before the hashing modes are defined, and to make the SHA-3 standard tree-hashing ready.

Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche

Reset Indifferentiability from Weakened Random Oracle Salvages One-Pass Hash Functions

Ristenpart et al. (EUROCRYPT 2011) showed that the indifferentiability theorem of Maurer et al. (TCC 2004) does not cover all multi-stage security notions; it only covers single-stage security notions. They defined reset indifferentiability, and proved the reset indifferentiability theorem, which covers all security notions; if a hash function is reset indifferentiable from a random oracle denoted by RO, for any security, any cryptosystem is at least as secure under the hash function as in the RO model. Unfortunately, they also proved the impossibility of one-pass hash functions such as ChopMD and Sponge; there exists a multi-security notion such that some cryptosystem is secure in the RO model but insecure when RO is replaced with a one-pass hash function.

In order to ensure other multi-stage security notions,we propose a new methodology, called the

$\mathcal{WRO}$

methodology, instead of the

$\mathcal{RO}$

methodology. We consider “Reset Indifferentiability from Weakened Random Oracle” which salvages ChopMD and Sponge. The concrete procedure of the

$\mathcal{WRO}$

methodology is as follows:

1

Define a new concept of

$\mathcal{WRO}$

instead of

$\mathcal{RO}$

,

2

Prove that a hash function

H

is reset indifferentiable from

$\mathcal{WRO}$

, (here the examples are ChopMD and Sponge), and

3

For multi-stage security G, prove that a cryptosystem

$\mathcal{C}$

is G-secure in the

$\mathcal{WRO}$

model.

As a result,

$\mathcal{C}$

with

H

is

$\mathcal{G}$

-secure by combining the results of Steps 2, 3, and the theorem of Ristenpart et al. Moreover, for a public-key encryption scheme (as

$\mathcal{C}$

) and the chosen-distribution attack game (as the game of

$\mathcal{G}$

) we prove that

$\mathcal{C(WRO)}$

is

$\mathcal{G}$

-secure, which implies the appropriateness of the new concept of the

$\mathcal{WRO}$

methodology.

Yusuke Naito, Kazuki Yoneyama, Kazuo Ohta

Cryptanalysis & Attacks (Symmetric Cryptography)

Memoryless Unbalanced Meet-in-the-Middle Attacks: Impossible Results and Applications

A meet-in-the-middle (MitM) attack is a popular tool for cryptanalysis. It independently computes two functions

$\mathcal{F}$

and

$\mathcal{G}$

, and finds a match of their outputs. When the cost of computing

$\mathcal{F}$

and

$\mathcal{G}$

are different, the problem is called unbalanced MitM attack. It is known that, for the balanced case, the MitM attack can be performed only with a negligible memory size without significantly increasing the computational cost by using the Floyd’s cycle-finding algorithm. It is also widely believed that the same technique can be applied to the unbalanced case, while no one has shown the evidence of its possibility yet. This paper contains two contributions. Firstly, we show an impossibility of the memoryless unbalanced MitM attack without significantly increasing the computational cost. The conversion to the memoryless attack with the Floyd’s cycle-finding algorithm always requires additional computational cost. Secondly, we find applications of the memoryless unbalanced MitM attack to show that it is still meaningful even with some additional computational cost. It can be used to generate multi-collisions of hash functions by using a dedicated collision attack algorithm. Our method finds 3-collisions of SHA-1 with 2

142

computations and negligible memory size, while the known best attack requires 2

106.6

computations and 2

53.3

memory size. The memoryless unbalanced MitM attack can also be applied to the limited-birthday distinguisher for hash functions.

Yu Sasaki

On the (In)Equivalence of Impossible Differential and Zero-Correlation Distinguishers for Feistel- and Skipjack-Type Ciphers

For many word-oriented block ciphers, impossible differential (ID) and zero-correlation linear (ZC) cryptanalyses are among the most powerful attacks. Whereas ID cryptanalysis makes use of differentials which never occur, the ZC cryptanalysis relies on linear approximations with correlations equal to zero. While the key recovery parts of ID and ZC attacks may differ and are often specific to the target cipher, the underlying distinguishing properties frequently cover the same number of rounds. However, in some cases, the discrepancy between the best known IDs and ZC approximations is rather significant.

At EUROCRYPT’13, a link between these two distinguishers has been presented. However, though being independent of the underling structure of the cipher, it is usually not useful for most known ID or ZC distinguishers. So despite the relevance of those attacks, the question of their equivalence or inequivalence has not been formally addressed so far in a constructive practical way.

In this paper, we aim to bridge this gap in the understanding of the links between the ID and ZC properties. We tackle this problem at the example of two wide classes of ciphers, namely, Feistel- and Skipjack-type ciphers. As our major contribution, for those ciphers, we derive conditions for impossible differentials and zero-correlation approximations to cover the same number of rounds. Using the conditions, we prove an equivalence between ID and ZC distinguishers for type-I and type-II Feistel-type ciphers, for Rule-A and Rule-B Skipjack-type ciphers, as well as for TWINE and LBlock. Moreover, we show this equivalence for the Extended Generalised Feistel construction presented at SAC’13. We also use our theoretical results to argue for an inequivalence between ID and ZC distinguishers for a range of Skipjack-type ciphers.

Céline Blondeau, Andrey Bogdanov, Meiqin Wang

Improved Cryptanalysis on Reduced-Round GOST and Whirlpool Hash Function

The GOST hash function family has served as the new Russian national hash standard (GOST R 34.11-2012) since January 1, 2013, and it has two members,

i

.

e

., GOST-256 and GOST-512 which correspond to two different output lengths. Most of the previous analyses of GOST emphasize on the compression function rather than the hash function. In this paper, we focus on security properties of GOST under the hash function setting. First we give two improved preimage attacks on 6-round GOST-512 compared with the previous preimage attack,

i

.

e

., a time-reduced attack with the same memory requirements and a memoryless attack with almost identical time. Then we improve the best collision attack on reduced GOST-256 (resp. GOST-512) from 5 rounds to 6.5 (resp. 7.5) rounds. Finally, we construct a limited-birthday distinguisher on 9.5-round GOST using the limited-birthday distinguisher on hash functions proposed at ASIACRYPT 2013. An essential technique used in our distinguisher is the carefully chosen differential trail, which can further exploit freedom degrees in the inbound phase when launching rebound attacks on the GOST compression function. This technique helps us to reduce the time complexity of the distinguisher significantly. We apply this strategy to Whirlpool, an ISO standardized hash function, as well. As a result, we construct a limited-birthday distinguisher on 9-round Whirlpool out of 10 rounds, and reduce the time complexity of the previous 7-round distinguisher. To the best of our knowledge, all of our results are the best cryptanalytic results on GOST and Whirlpool in terms of the number of rounds analyzed under the hash function setting.

Bingke Ma, Bao Li, Ronglin Hao, Xiaoqian Li

Differential Cryptanalysis and Linear Distinguisher of Full-Round Zorro

Zorro is an AES-like lightweight block cipher proposed in CHES 2013, which only uses 4 S-boxes per round. The designers showed the resistance of the cipher against various attacks and concluded the cipher has a large security margin. Recently, Guo et. al [1] have given a key recovery attack on full-round Zorro by using the internal differential characteristics. However, the attack only works for 2

64

out of 2

128

keys. In this paper, the secret key selected randomly from the whole key space can be recovered much faster than the brute-force attack. We first observe that the fourth power of the MDS matrix used in Zorro(or AES) equals to the identity matrix. Moveover, several iterated differential characteristics and iterated linear trails are found due to the interesting property. We select three characteristics with the largest probability to give the key recovery attack on Zorro and a linear trail with the largest correlation to show a linear distinguishing attack with 2

105.3

known plaintexts. The results show that the security of Zorro against linear and differential cryptanalysis evaluated by designers is insufficient and the security margin of Zorro is not enough.

Yanfeng Wang, Wenling Wu, Zhiyuan Guo, Xiaoli Yu

Detecting Hidden Leakages

Reducing the entropy of the mask is a technique which has been proposed to mitigate the high performance overhead of masked software implementations of symmetric block ciphers. Rotating S-box Masking (RSM) is an example of such schemes applied to AES with the purpose of maintaining the security at least against univariate first-order side-channel attacks. This article examines the vulnerability of a realization of such technique using the side-channel measurements publicly available through DPA contest V4. Our analyses which focus on exploiting the first-order leakage of the implementation discover a couple of potential attacks which can recover the secret key. Indeed the leakage we exploit is due to a design mistake as well as the characteristics of the implementation platform, none of which has been considered during the design of the countermeasure (implemented in naive

C

code).

Amir Moradi, Sylvain Guilley, Annelie Heuser

Network Security

Improving Intrusion Detection Systems for Wireless Sensor Networks

A considerable amount of research has been undertaken in the field of intrusion detection in wireless sensor networks. Researchers proposed a number of relevant mechanisms, and it is not an easy task to select the right ones for a given application scenario. Even when a network operator knows what mechanism to use, it remains an open issue how to configure this particular mechanism in such a way that it is efficient for the particular needs. We propose a framework that optimizes the configuration of an intrusion detection system in terms of detection accuracy and memory usage. There is a variety of scenarios, and a single set of configuration values is not optimal for all of them. Therefore, we believe, such a framework is of a great value for a network operator who needs to optimize an intrusion detection system for his particular needs, e.g., attacker model, environment, node parameters.

Andriy Stetsko, Tobiáš Smolka, Vashek Matyáš, Martin Stehlík

MoTE-ECC: Energy-Scalable Elliptic Curve Cryptography for Wireless Sensor Networks

Wireless Sensor Networks (WSNs) are susceptible to a wide range of malicious attacks, which has stimulated a body of research on “light-weight” security protocols and cryptographic primitives that are suitable for resource-restricted sensor nodes. In this paper we introduce MoTE-ECC, a highly optimized yet scalable ECC library for Memsic’s MICAz motes and other sensor nodes equipped with an 8-bit AVR processor. MoTE-ECC supports scalar multiplication on Montgomery and twisted Edwards curves over Optimal Prime Fields (OPFs) of variable size, e.g. 160, 192, 224, and 256 bits, which allows for various trade-offs between security and execution time (resp. energy consumption). OPFs are a special family of “low-weight” prime fields that, in contrast to the NIST-specified fields, facilitate a parameterized implementation of the modular arithmetic so that one and the same software function can be used for operands of different length. To demonstrate the performance of MoTE-ECC, we take (ephemeral) ECDH key exchange between two nodes as example, which requires each node to execute two scalar multiplications. The first scalar multiplication is performed on a fixed base point (to generate a key pair), whereas the second scalar multiplication gets an arbitrary point as input. Our implementation uses a fixed-base comb method on a twisted Edwards curve for the former and a simple ladder approach on a birationally-equivalent Montgomery curve for the latter. Both scalar multiplications require about 9 ·10

6

clock cycles in total and occupy only 380 bytes in RAM when the underlying OPF has a length of 160 bits. We also describe our efforts to harden MoTE-ECC against side-channel attacks (e.g. simple power analysis) and introduce a highly regular implementation of the comb method.

Zhe Liu, Erich Wenger, Johann Großschädl

BackRef: Accountability in Anonymous Communication Networks

Many anonymous communication networks (ACNs) rely on routing traffic through a sequence of proxy nodes to obfuscate the originator of the traffic. Without an accountability mechanism, exit proxy nodes may become embroiled in a criminal investigation if originators commit criminal actions through the ACN. We present

BackRef

, a generic mechanism for ACNs that provides practical repudiation for the proxy nodes by tracing back the selected outbound traffic to the predecessor node (but not in the forward direction) through a cryptographically verifiable chain. It also provides an option for full (or partial) traceability back to the entry node or even to the corresponding originator when all intermediate nodes are cooperating. Moreover, to maintain a good balance between anonymity and accountability, the protocol incorporates whitelist directories at exit proxy nodes.

BackRef

offers improved deployability over the related work, and introduces a novel concept of pseudonymous signatures that may be of independent interest.

We exemplify the utility of

BackRef

by integrating it into the onion routing (OR) protocol, and examine its deployability by considering several system-level aspects. We also present the security definitions for the

BackRef

system (namely, anonymity, backward traceability, no forward traceability, and no false accusation) and conduct a formal security analysis of the OR protocol with

BackRef

using ProVerif, an automated cryptographic protocol verifier, establishing the aforementioned security properties against a strong adversarial model.

Michael Backes, Jeremy Clark, Aniket Kate, Milivoj Simeonovski, Peter Druschel

WebTrust – A Comprehensive Authenticity and Integrity Framework for HTTP

HTTPS is

the

standard for confidential and integrity-protected communication on the Web. However, it authenticates the server, not its content. We present WebTrust, the first comprehensive authenticity and integrity framework that allows on-the-fly verification of static, dynamic, and real-time streamed Web content from untrusted servers. Our framework seamlessly integrates into HTTP and allows to validate streamed content progressively at arrival. Our performance results demonstrate both the practicality and efficiency of our approach.

Michael Backes, Rainer W. Gerling, Sebastian Gerling, Stefan Nürnberger, Dominique Schröder, Mark Simkin

Signatures

A Revocable Group Signature Scheme from Identity-Based Revocation Techniques: Achieving Constant-Size Revocation List

Any multi-user cryptographic primitives need revocation since a legitimate user may quit the organization, or may turn to be malicious, or the key may be leaked. In the group signature context, usually group manager publishes the revocation list that contains revocation tokens. Since signers/verifiers need to obtain the revocation list in

each revocation epoch

for generating/verifying a group signature, a small-size revocation list is really important in practice. However, all previous revocable group signatures require at least

O

(

r

)-size revocation list, where

r

is the number of revoked users. In this paper, we propose the first revocable group signature scheme with the constant size revocation list from identity-based revocation (IBR) techniques. We use an IBR scheme proposed by Attrapadung-Libert-Panafieu (PKC2011) as a building block. Although the maximum number of the revoked users needs to be fixed in the setup phase, however, the maximum number of group members is potentially unbounded (as in IBR). This property has not been achieved in the recent scalable revocable group signature schemes, and seems to be of independent interest.

Nuttapong Attrapadung, Keita Emura, Goichiro Hanaoka, Yusuke Sakai

Faster Batch Verification of Standard ECDSA Signatures Using Summation Polynomials

Several batch-verification algorithms for original ECDSA signatures are proposed for the first time in AfricaCrypt 2012. Two of these algorithms are based on the naive idea of taking square roots in the underlying fields, and the others perform symbolic manipulation to verify small batches of ECDSA signatures. In this paper, we use elliptic-curve summation polynomials to design a new ECDSA batch-verification algorithm which is theoretically and experimentally much faster than the symbolic algorithms of AfricaCrypt 2012. Our experiments on NIST prime and Koblitz curves demonstrate that our proposed algorithm increases the optimal batch size from seven to nine. We also mention how our algorithm can be adapted to Edwards curves.

Sabyasachi Karati, Abhijit Das

On Updatable Redactable Signatures

Redactable signatures allow removing parts from signed documents. State-of-the-art security models do not capture the possibility that the signer can “update” signatures, i.e., add new elements. Neglecting this, third parties can generate forgeries. Moreover, there are constructions which permit creating a signature by merging two redacted messages, if they stem from the same original. Our adjusted definition captures both possibilities. We present a provably secure construction in the standard model, which makes use of a novel trapdoor-accumulator.

Henrich C. Pöhls, Kai Samelin

Practical Signatures from the Partial Fourier Recovery Problem

We present PASS

RS

, a variant of the prior PASS and PASS-2 proposals, as a candidate for a practical post-quantum signature scheme. Its hardness is based on the problem of recovering a ring element with small norm from an incomplete description of its Chinese remainder representation. For our particular instantiation, this corresponds to the recovery of a vector with small infinity norm from a limited set of its Fourier coefficients.

The key improvement over previous versions of PASS is the introduction of a rejection sampling technique from Lyubashevsky (2009) which assures that transcript distributions are completely decoupled from the keys that generate them.

Although the scheme is not supported by a formal security reduction, we present extensive arguments for its security and derive concrete parameters based on the performance of state of the art lattice reduction and enumeration techniques.

Jeff Hoffstein, Jill Pipher, John M. Schanck, Joseph H. Silverman, William Whyte

System Security

Activity Spoofing and Its Defense in Android Smartphones

Smartphones have become ubiquitous in today’s digital world as a mobile platform allowing anytime access to email, social platforms, banking, and shopping. Many providers supply native applications as a method to access their services, allowing users to login directly through a downloadable app. In this paper, we first expose a security vulnerability in the Android framework that allows for third party apps to spoof native app activities, or screens. This can lead to a wide variety of security risks including the capture and silent exfiltration of login credentials and private data. We then compare current defense mechanisms, and introduce the concept of Trusted Activity Chains as a lightweight protection against common spoofing attacks. We develop a proof of concept implementation and evaluate its effectiveness and performance overhead.

Brett Cooley, Haining Wang, Angelos Stavrou

Polymorphism as a Defense for Automated Attack of Websites

We propose PolyRef, a method for a polymorphic defense to defeat automated attacks on web applications. Many websites are vulnerable to automated attacks. Basic anti-automation countermeasures such as Turing tests provide minimal efficacy and negatively impact the usability and the accessibility of the protected application. Motivated by the observation that many automated attacks rely on interaction with the publicly visible code transmitted to the browser, PolyRef proposes to make critical elements of the underlying webpage code polymorphic, rendering machine automation impractical to implement. We categorize the threats that rely on automation and the available anti-automation approaches. We present two techniques for using polymorphism as an anti-automation defense.

Xinran Wang, Tadayoshi Kohno, Bob Blakley

Fragmentation Considered Leaking: Port Inference for DNS Poisoning

Internet systems and networks have a long history of attacks by off-path adversaries. An off-path adversary cannot see the traffic exchanged by the legitimate end points, and in the course of an attack it attempts to impersonate some victim by injecting spoofed packets into the communication flow. Such attacks subvert the correctness and availability of Internet services and, among others, were applied for DNS cache poisoning, TCP injections, reflection DDoS attacks.

A significant research effort is aimed at hardening client systems against off-path attacks by designing challenge-response defences, whereby random challenges are sent with the request and the responses are validated to echo the corresponding values.

In this work we study the security of a standard and widely deployed challenge-response defence port randomisation, and show that off-path attackers can

efficiently

and

stealthily

learn the ports selected by end systems.

We show how to apply our techniques for DNS cache poisoning. We tested our attacks against standard and patched operating systems and popular DNS resolvers software. Our results motivate speeding up adoption of cryptographic defences for DNS.

Haya Shulman, Michael Waidner

Secure Computation

Delegating a Pairing Can Be Both Secure and Efficient

Bilinear pairings have been widely used in cryptographic protocols since they provide very interesting functionalities in regard of identity based cryptography, short signatures or cryptographic tools with complex properties. Unfortunately their implementation on limited devices remains complex and even if a lot of work has been done on the subject, the current results in terms of computational complexity may still be prohibitive. This is clearly not for today to find the implementation of a bilinear pairing in every smart card. One possibility to avoid this problem of efficiency is to delegate the pairing computation to a third party. The result should clearly be both secure and efficient. Regarding security, the resulting computation of a pairing

e

(

A

,

B

) by the third party should be verifiable by the smart card. Moreover, if the points

A

and/or

B

are secret at the beginning of the protocol, they should also be secret after its execution. Regarding efficiency, besides some specific cases, existing protocols for delegating a pairing are costlier than a true embedded computation inside the smart card. This is due to the fact that they require several exponentiations to check the validity of the result.

In this paper we first propose a formal security model for the delegation of pairings that fixes some weakness of the previous models. We also provide efficient ways to delegate the computation of a pairing

e

(

A

,

B

), depending on the status of

A

and

B

. Our protocols enable the limited device to verify the value received from the third party with mostly one exponentiation and can be improved to also ensure secrecy of

e

(

A

,

B

).

Sébastien Canard, Julien Devigne, Olivier Sanders

Automatic Protocol Selection in Secure Two-Party Computations

Performance of secure computation is still often an obstacle to its practical adaption. There are different protocols for secure computation that compete for the best performance. In this paper we propose

automatic protocol selection

which selects a protocol for each operation resulting in a mix with the best performance so far. Based on an elaborate performance model, we propose an optimization algorithm and an efficient heuristic for this selection problem. We show that our mixed protocols achieve the best performance on a set of use cases. Furthermore, our results underpin that the selection problem is so complicated and large in size, that a programmer is unlikely to manually make the optimal selection. Our proposed algorithms nevertheless can be integrated into a compiler in order to yield the best (or near-optimal) performance.

Florian Kerschbaum, Thomas Schneider, Axel Schröpfer

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise