Information Security and Privacy: 15th Australasian Conference, ACISP 2010, Sydney, Australia, July 5-7, 2010, Proceedings (Lecture Notes in Computer Science, 6168)

The annual Australasian Conference on Information Security and Privacy is the premier Australian academic conference in its ?eld, showcasing research from around the globe on a range of topics. ACISP 2010 was held during July 5-7, 2010, at Macquarie University in Sydney, Australia. There were 97 paper submissions for the conference. These submission were reviewed by the Program Committee and a number of other individuals, whose namescanbefoundoverleaf.TheProgramCommitteethenselected24papersfor presentationatthe conference.Thesepapersarecontainedin theseproceedings. In addition to the peer-reviewedpapers, two invited speakers presented talks at the conference: Craig Gentry (IBM, USA); and Stephan Overbeek (Shear- ter Solutions, Australia). We would like to express our gratitude to Craig and Stephan for contributing their knowledge and insight, and thus expanding the horizons of the conference delegates. We would like to thank the authors of all of submission for o?ering their researchforpublicationinACISP2010.WeextendoursincerethankstotheP- gram Committee and other reviewers for the high-quality reviews and in-depth discussion. The Program Committee made use of the iChair electronic subm- sion and reviewing software written by Thomas Baign eres and Matthieu Finiasz at EPFL, LASEC. We would like to express our thanks to Springer for conti- ing to support the ACISP conference and for help in the conference proceedings production. We also thank the Organizing Committee, led by the ACISP 2010 General Chair Josef Pieprzyk, for their contribution to the conference. Title Preface Organization Table of Contents Symmetric Key Encryption Cryptanalysis of a Generalized Unbalanced Feistel Network Structure Introduction Description of n-Cell GF-NLFSR Encryption Property of n-Cell GF-NLFSR Integral Distinguisher of GF-NLFSR Preliminaries n$^2$-Round Integral Distinguisher of n-Cell GF-NLFSR Impossible Differential of GF-NLFSR A Kind of Non-surjective Attack Description of the Non-surjective Distinguisher Description of the Non-surjective Attack Experiments with the Proposed Non-surjective Attack Conclusion References Improved Algebraic Cryptanalysis of QUAD, Bivium and Trivium via Graph Partitioning on Equation Systems Introduction Preliminaries Graph Connectivity Graph Partitioning Partitioning Algorithms and Software Partitioning Polynomial Systems Graph Partitioning Experiments Applications to Algebraic Cryptanalysis QUAD Trivium Conclusions References On Multidimensional Linear Cryptanalysis Introduction Notations and Background Statistical Model and Algorithm of Hermelin et al. Constructing Multidimensional Probability Distribution Multidimensional Generalization of Matsui’s Alg. 1 The Improvements A Formula for N, the Number of Samples Required Analysis of the Multidimensional Alg. 1 in [10] Fast Computation of Empirical Distribution – Method A Fast Computation of Kullback-Leibler Distance – Method B Efficiency of the Improved Algorithm Application to Cryptanalysis Application to the 4-Round Serpent Scenario Multidimensional Linear Cryptanalysis of 9-Round Serpent Conclusions References Side-Channel Analysis of the K2 Stream Cipher Introduction Specification Implementation Aspects An Observation on LFSR-Based Stream Ciphers Timing Attacks K2 and Conventional Timing Attacks K2 and Cache-Timing Attacks Power Analysis Simple Power Analysis Countermeasures Fault Analysis Related Work Attacking FSR-A and FSR-B of K2 Attacking the FSM Conclusion References On Unbiased Linear Approximations Introduction Linear Approximations Key Recovery Using Entangled Approximations Success Rates in Using Entangled Approximations Experimental Confirmation Entangled Approximations and Large Data Sets Experimental Confirmation Separating Plaintext and Ciphertext Discussion Conclusions References Hash Functions Distinguishers for the Compression Function and Output Transformation of Hamsi-256 Introduction Description of Hamsi-256 High-Level Structure Internals of the Compression Function of Hamsi Higher-Order Differential Analysis Definitions On the Degree of the Compression Function Finding k-sums for the Compression Function Finding Zero-Sums for the Output Permutation First Order Differential Analysis Differential Properties of the Sbox Differential Properties of the Linear Transform L Near-Collisions for the Compression Function Automated Differential Path Search Non-randomness of the Ouput Transformation The Differential Path First Round and Message Expansion Last Round and Truncation Distinguishing the Output Transformation Conclusion References Second-Preimage Analysis of Reduced SHA-1 Introduction and Overview Motivation: Security Margin of SHA-1 against Preimage Style Attacks The Contribution Preview of Our Results on SHA-1 Related Work Outline of the Paper Definitions Description of SHA-1 Message Expansion State Update Transformation Violating Second Preimage Resistance Properties with Differentials Application to SHA-1 Hash Function Attacks: 34-Step SHA-1 as a Case Study Compression Function Attacks: 61-Step SHA-1 Discussion and Open Problems References Some Observations on Indifferentiability Introduction (In)Security in the Indifferentiability World Indifferentiability from a Random Oracle Concatenation of Random Oracles: $RO$ − $RO$ NMAC: MD$_RO$−$RO$ Design Principles for Secure Hash Functions Discussion and Conclusion The Ambiguity of Indifferentiability in the Design of Practical Hash Functions Conclusions References Public Key Cryptography Adaptive and Composable Non-committing Encryptions Introduction The State-of-the-Art This Work Non-committing Encryptions: Functionality and Security Definition The Universally Composable Framework Functionality of Non-commitment Encryptions Preliminaries The Naor-Pinkas Randomizer The Oblivious Sampling and Faking Algorithms Universally Composable Non-committing Encryptions The Description of Non-committing Encryptions The Proof of Security Conclusion References Relations among Notions of Complete Non-malleability: Indistinguishability Characterisation and Efficient Construction without Random Oracles Introduction Preliminaries Defining Strong Decryption Oracles Security under Strong Chosen-Ciphertext Attacks Indistinguishability of Ciphertexts Complete Non-malleability Relations among Notions of Security An Efficient Completely Non-Malleable Scheme References Strong Knowledge Extractors for Public-Key Encryption Schemes Introduction Related Work Preliminaries Strong Chosen-Ciphertext Security Security under Invert and Chosen-Ciphertext Attacks Extractor-Based Properties Strong Plaintext Awareness Secret Key Awareness Secret Key Aware Schemes Generic Construction with a Random Oracle Towards Secret-Key-Aware Schemes without Random Oracles References A Multi-trapdoor Commitment Scheme from the RSA Assumption Introduction Background Our Contributions and Constructions Related Works and Comparisons Preliminaries Notations and Conventions Indistinguishability Complexity Assumptions Signature Schemes Σ-Protocol for Waters Signature [11] Commitment Scheme Description of a Commitment Scheme from the CDH Assumption The Construction from the RSA Assumption Description of a Commitment Scheme from the RSA Assumption Security Proof of RSACom Conclusion References Identity-Based Chameleon Hash Scheme without Key Exposure Introduction Preliminaries Bilinear Pairings and Number-Theoretic Problems Proofs of Knowledge Definitions Identity-Based Chameleon Hashing Security Requirements Identity-Based Key-Exposure Free Chameleon Hashing The Proposed Identity-Based Chameleon Hash Scheme Security Analysis Conclusions References The Security Model of Unidirectional Proxy Re-Signature with Private Re-Signature Key Introduction What Is Proxy Re-Signature? Applications of PRS History of Proxy Re-Signatures This Paper’s Contributions Definitions Unidirectional Proxy Re-Signature with Private Re-Signature Key The AH Model On the AH Model Bilinear Groups Complexity Assumption The Scheme S$_us$ Correctness Security Analysis An Attack on Scheme S$_us$ The Proposed Security Model for $UPRS-prk$ Conclusions References Security Estimates for Quadratic Field Based Cryptosystems Introduction Arithmetic in Quadratic Fields Solving the Discrete Logarithm Problems Implementation and Numerical Results Security Estimates Conclusions References Solving Generalized Small Inverse Problems Introduction Our Contribution Organization Preliminaries Small Secret Exponent Attack on RSA [2] LLL Algorithm and Howgrave-Graham’s Lemma How to Solve Generalized Small Inverse Problem Lattice-Based Algorithm for (I) How to Solve (II) Proof of Theorem 1 Small Example of Our Compiler Deriving a Condition for Solving GSIP Application of Our Compiler to RSA-Related Cryptanalysis Concluding Remarks and Open Problems References Protocols One-Time-Password-Authenticated Key Exchange Introduction Related Work Security of One-Time-Password Protocols Security Model A Generic Construction for One-Time Password Protocols Construction of 1(P) from P Security of 1(P) Efficiency and Practicality of 1(P) Using Pseudorandom Passwords Using Time-Dependent Pseudorandom Passwords Analysis of the OPKeyX Protocol Conclusions References Predicate-Based Key Exchange Introduction Contributions Motivation Related Work Notation Predicate-Based Key Exchange Correctness Security Model Implementation Issues Predicate-Based Signature Schemes A Signed Diffie-Hellman Construction Protocol Definition Credential Privacy Session Key Security Conclusions References Attribute-Based Authenticated Key Exchange Introduction Contributions Related Work Organization Encapsulation Policy Attribute-Based KEM Security Model A Chosen Ciphertext Secure EP-AB-KEM Attribute-Based Authenticated Key Exchange A Generic One-Round AB-AKE Protocol Extensions AKE-Security with Forward Secrecy Constructing AB-AKE Protocols with Forward Secrecy Conclusion References Optimally Tight Security Proofs for Hash-Then-Publish Time-Stamping Introduction Notation Hash-then-Publish Time-Stamping Security Condition for Time-Stamping Schemes Hash Tree Time-Stamping Schemes Existing Security Proofs Tightness Measure for Security Reductions Reduction with Quadratic Security Loss Reducing the Power of N New Reduction Problems with Establishing a Linear Reduction Tightness Bounds for Security Reductions New Reduction: The Case N = 1 New Reduction: General Case New Reduction: Reducing the Power of N Practical Implications References Additive Combinatorics and Discrete Logarithm Based Range Protocols Introduction Preliminaries Sumset-Representation of Integer Intervals Preliminaries: CCS Range Proof ModifiedRangeProof: New Comparison of Case Analysis Conclusions References Proof-of-Knowledge of Representation of Committed Value and Its Applications Introduction RelatedWork Overview of Our Approach Organization of the Paper Preliminaries Notations Bilinear Map Number-Theoretic Assumptions Cryptographic Tools A Zero-Knowledge Proof-of-Knowledge Protocol for RCV The Actual Protocol Efficiency Analysis of PK$_RCV$ Application to Round-Optimal Concurrently-Secure Blind Signature without Interactive Assumptions Syntax Construction Application to Traceable Signatures with Concurrent Join Syntax Construction Compact E-Cash with Concurrent Withdrawal Conclusion References Network Security Pattern Recognition Techniques for the Classification of Malware Packers Introduction Background Packing Packer Evolution Traditional Signature Based Packer Classification Pattern Recognition RelatedWork Methodology Feature Extraction Classification Experiments and Results Data Sets EvaluationMetrics Pattern Recognition Results Conclusions and Future Work References Repelling Sybil-Type Attacks in Wireless Ad Hoc Systems Introduction Algorithm Description Algorithm Analysis Effectiveness of Cheater Detection Adversary’s Optimal Strategy FinalRemarks References Author Index Annotation. This book constitutes the refereed proceedings of the 15th Australasian Conference on Information Security and Privacy, ACISP 2010, held in Sydney, Australia, in July 2010. The 24 revised full papers presented were carefully reviewed and selected from 97 submissions. The papers are organized in topical sections on symmetric key encryption; hash functions; public key cryptography; protocols; and network security