Visible to the public Black Box Cryptography 2015Conflict Detection Enabled

SoS Newsletter- Advanced Book Block


SoS Logo

Black Box Cryptography



According to Stack Exchange, black box security is “security of a cryptographic algorithm studied in the ‘black-box’ model: e.g., for symmetric encryption, the attacker is given access to a ‘device’ which runs the encryption algorithm with a given key, and can submit plaintexts and ciphertexts, the goal of the attacker being to be able to decrypt a given block without submitting that exact block as ciphertext.” For the Science of Security community, back box cryptography is important to composability, metrics, and resilience. The work cited here was presented in 2013–2016.

S. Garg, S. Lu and R. Ostrovsky, “Black-Box Garbled RAM,” Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, Berkeley, CA, 2015, vol., no., pp. 210-229. doi:10.1109/FOCS.2015.22
Abstract: Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, thereby avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao’s garbled circuit construction, except that known realizations of Garbled RAM make non-black-box use of the underlying cryptographic primitives. In this paper we remove this limitation and provide the first black-box construction of Garbled RAM with polylogarithmic overhead. Our scheme allows for garbling multiple RAM programs being executed on a persistent database and its security is based only on the existence of one-way functions. We also obtain the first secure RAM computation protocol that is both constant round and makes only black-box use of one-way functions in the Oblivious Transfer hybrid model.
Keywords: cryptographic protocols; RAM computation protocol; black-box construction; black-box garbled RAM; cryptographic primitives; oblivious transfer hybrid model; one-way functions; persistent database; polylogarithmic overhead; random access machine program; Central Processing Unit; Complexity theory; Computer science; Cryptography; Databases; Random access memory; Black-Box Cryptography; Garbled RAM; One-Way Functions; Secure Computation (ID#: 16-10872)


G. Asharov and G. Segev, “Limits on the Power of Indistinguishability Obfuscation and Functional Encryption,” Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, Berkeley, CA, 2015, pp. 191-209. doi:10.1109/FOCS.2015.21
Abstract: Recent breakthroughs in cryptography have positioned indistinguishability obfuscation as a “central hub“ for almost all known cryptographic tasks, and as an extremely powerful building block for new cryptographic tasks resolving long-standing and foundational open problems. However, constructions based on indistinguishability obfuscation almost always rely on non-black-box techniques, and thus the extent to which it can be used as a building block in cryptographic constructions has been completely unexplored so far. We present a framework for proving meaningful negative results on the power of indistinguishability obfuscation. By considering indistinguishability obfuscation for oracle-aided circuits, we capture the common techniques that have been used so far in constructions based on indistinguishability obfuscation. These include, in particular, non-black-box techniques such as the punctured programming approach of Sahai and Waters (STOC ’14) and its variants, as well as sub-exponential security assumptions. Within our framework we prove the first negative results on the power of indistinguishability obfuscation and of the tightly related notion of functional encryption. Our results are as follows: There is no fully black-box construction of a collision-resistant function family from an indistinguishability obfuscator for oracle-aided circuits. There is no fully black-box construction of a key-agreement protocol with perfect completeness from a private-key functional encryption scheme for oracle-aided circuits. Specifically, we prove that any such potential constructions must suffer from an exponential security loss, and thus our results cannot be circumvented using sub-exponential security assumptions. Our framework captures constructions that may rely on a wide variety of primitives in a non-black-box manner (e.g., Obfuscating or generating a functional key for a function that uses the evaluation circuit of a puncturable pseudorandom function), and we only assume that the underlying indistinguishability obfuscator or functional encryption scheme themselves are used in a black-box manner.
Keywords: exponential distribution; private key cryptography; random sequences; exponential security loss; indistinguishability obfuscation; nonblack-box technique; oracle-aided circuit; private-key functional encryption scheme; pseudorandom function; Encryption; Integrated circuit modeling; Protocols; Public key; Standards (ID#: 16-10873)


H. Bruyninckx, F. Lafitte and D. Van Heule, “Safe Cryptographic Random Number Generation Using Untrusted Generators,” Communications (ICC), 2014 IEEE International Conference on, Sydney, NSW, 2014, vol., no., pp. 731-736. doi:10.1109/ICC.2014.6883406
Abstract: The security of many cryptographic applications relies heavily on the quality of the random numbers used. Therefore, random number generation is one of the most critical primitives for cryptography. This paper focuses on true random number generators (TRNGs) and the analysis of their security requirements. After illustrating issues associated with adversarial influences on TRNGs, we propose a simple method to obtain a secure TRNG based on n TRNGs originating from (potentially) untrusted vendors. The untrusted generators are combined such that as long as one out of the n vendors does not collude with the other vendors, the generator is secure, i.e., the output is unpredictable and uniformly distributed even in the presence of an active attacker. In order to achieve this, we review several choices of functions to be used as combiner. The advantage of our design is that only the (black-box) input-output behavior of the vendor’s TRNGs needs to be evaluated. No overhead is introduced by the combiner. The resulting generator offers fault resilience and ease of maintenance.
Keywords: cryptography; random number generation; TRNGs; active attacker; cryptographic random number generation; fault resilience; true random number generators; untrusted generators; Boolean functions; Correlation; Cryptography; Entropy; Generators; Noise; Attacks on TRNGs; Cryptography; Fault-tolerance; Hardware Trojans; Random Number Generator (RNG); Resilient functions (ID#: 16-10874)


Y. Ren and L. Wu, “Power Analysis Attacks on Wireless Sensor Nodes Using CPU Smart Card,” Wireless and Optical Communication Conference (WOCC), 2013 22nd, Chongqing, 2013, vol., no., pp. 665-670. doi:10.1109/WOCC.2013.6676458
Abstract: In wireless sensor networks (WSN), CPU smart cards can be used as crypto accelerators and temper-resistant storages to improve security. But Side Channel Attacks (SCA) can bypass temper-resistant mechanisms and recover the confidential information without being detected. In this work, a typical black-box Side Channel Attack (SCA) on a real-life 32-Bit CPU smart card against Triple Data Encryption Standard (3DES) is successfully conducted, and the whole 112 key bits of 3DES are recovered with moderate effort which is around 80,000 power traces. Our result highlights that SCA is a practical threat in the security of WSN, and proper countermeasures against SCA should be used.
Keywords: cryptography; microprocessor chips; smart cards; wireless sensor networks; 3DES; CPU smart cards; SCA; WSN; crypto accelerators; power analysis attacks; side channel attacks; tamper-resistant mechanisms; tamper-resistant storages; triple data encryption standard; wireless sensor nodes; 3DES; CPU smart card; side channel attack (SCA); wireless sensor network (WSN) (ID#: 16-10875)


S. Arul Oli and L. Arockiam, “A Framework for Key Management for Data Confidentiality in Cloud Environment,” Computer Communication and Informatics (ICCCI), 2015 International Conference on, Coimbatore, 2015, vol., no., pp. 1-4. doi:10.1109/ICCCI.2015.7218116
Abstract: Cloud computing is a technique to keep the resources intact and available with internet facilities online at anytime and anywhere. A user may access cloud services as a utility service and can use them almost instantly. These features make cloud computing so flexible with easy access for unlimited users with several potential risks, thus demanding for the security mechanisms. Hence the need for cryptographic algorithm is inevitable for the transaction of data in a more secure manner, providing confidentiality and integrity of the data to the users. There are many numbers of cryptographic algorithms that make the system protected from the attacks of intruders. With the use of cryptographic algorithms, the keys are generated and the techniques are introduced to manage these generated keys. We make all the impossibility by use of management techniques for the intruders to break the key. These techniques act as a black box where the intruders have not even slightest glue for the key identification. In this paper the key management mechanisms are introduced which would help the users to manage the generated keys to protect the data in terms of confidentiality in cloud storage.
Keywords: cloud computing; data integrity; management science; private key cryptography; Internet facilities; cloud computing; cloud environment; cloud services; cryptographic algorithm; data confidentiality; data integrity; key identification; key management; security mechanisms; utility service; Cloud computing; Computer science; Computers; Encryption; Informatics; Cryptography; Cryptosystems; Data security; Key management (ID#: 16-10876)


T. Nakasone, Y. Li, K. Ohta and K. Sakiyama, “Exploration of the CC-EMA Attack Towards Efficient Evaluation of EM Information Leakage,” Electromagnetic Compatibility (EMC EUROPE), 2013 International Symposium on, Brugge, 2013, vol., no., pp. 411-414. doi: (not provided)
Abstract: This paper discusses the efficiency of the CC-EMA (Clockwise Collision based ElectroMagnetic Analysis) attack on hardware implementation of 128-bit AES (Advanced Encryption Standard) block cipher. The analysis efficiency of CC-EMA was first discussed on a white-box setting, i.e., using a known-key AES (Advanced Encryption Standard) hardware [10]. Then, more realistic attack scenario was applied for CC-EMA, where the secret key of AES hardware was unknown, i.e., black-box analysis, and the attack efficiency in the key recovery was briefly discussed in [11]. In this paper, we revisit the previous work for CC-EMA and explore the attack efficiency of CC-EMA furthermore in order to evaluate the information leakage from proximal EM measurements of IC (Integrated Circuit) devices. In order to evaluate the attack efficiency under various attack environments, we construct a simulation environment, where the intensity of EM radiation is parameterised assuming that it follows a normal distribution. As a result, we show that CC-EMA attack delivers equal or superior performance in the key recovery compared to the CEMA (Correlation EMA) attack and the key can be recovered by CC-EMA with less than 1100 EM measurements, in such case that the EM intensity for CC could be measured distinctly.
Keywords: cryptography; integrated circuits; normal distribution; 128-bit AES block cipher; CC-EMA attack; EM radiation intensity; IC devices; advanced encryption standard; attack efficiency; black-box analysis; clockwise collision based electromagnetic analysis attack; information leakage evaluation; integrated circuit devices; normal distribution; proximal EM measurements; Clocks; Cryptography; Electromagnetic compatibility; Hardware; High definition video; Integrated circuit modeling; Registers (ID#: 16-10877)


K. M. Chung, R. Ostrovsky, R. Pass and I. Visconti, “Simultaneous Resettability from One-Way Functions,” Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, Berkeley, CA, 2013, vol., no., pp. 60-69. doi:10.1109/FOCS.2013.15
Abstract: Resettable-security, introduced by Canetti, Goldreich, Goldwasser and Micali (STOC’00), considers the security of cryptographic two-party protocols (in particular zero-knowledge arguments) in a setting where the attacker may “reset” or “rewind” one of the players. The strongest notion of resettable security, simultaneous resettability, introduced by Barak, Goldreich, Goldwasser and Lindell (FOCS’01), requires resettable security to hold for both parties: in the context of zero-knowledge, both the soundness and the zero-knowledge conditions remain robust to resetting attacks. To date, all known constructions of protocols satisfying simultaneous resettable security rely on the existence of ZAPs; constructions of ZAPs are only known based on the existence of trapdoor permutations or number-theoretic assumptions. In this paper, we provide a new method for constructing protocols satisfying simultaneous resettable security while relying only on the minimal assumption of one-way functions. Our key results establish, assuming only one-way functions: Every language in NP has an ω(1)-round simultaneously resettable witness indistinguishable argument system; Every language in NP has a (polynomial-round) simultaneously resettable zero-knowledge argument system. The key conceptual insight in our technique is relying on black-box impossibility results for concurrent zero-knowledge to achieve resettable-security.
Keywords: computational complexity; cryptographic protocols; number theory; ω(1)-round simultaneously resettable witness indistinguishable argument system; NP; ZAP; black-box impossibility results; cryptographic two-party protocols; number-theoretic assumptions; one-way functions; polynomial-round simultaneously resettable zero-knowledge argument system; simultaneous resettable security; trapdoor permutations; zero-knowledge conditions; Cryptography; Polynomials; Probabilistic logic; Protocols; Schedules; Standards; proof systems; resettable WI/ZK/soundness (ID#: 16-10878)


S. Choi, D. Zage, Y. R. Choe and B. Wasilow, “Physically Unclonable Digital ID,” Mobile Services (MS), 2015 IEEE International Conference on, New York, NY, 2015, vol., no., pp. 105-111. doi:10.1109/MobServ.2015.24
Abstract: The Center for Strategic and International Studies estimates the annual cost from cyber crime to be more than $400 billion. Most notable is the recent digital identity thefts that compromised millions of accounts. These attacks emphasize the security problems of using clonable static information. One possible solution is the use of a physical device known as a Physically Unclonable Function (PUF). PUFs can be used to create encryption keys, generate random numbers, or authenticate devices. While the concept shows promise, current PUF implementations are inherently problematic: inconsistent behavior, expensive, susceptible to modeling attacks, and permanent. Therefore, we propose a new solution by which an unclonable, dynamic digital identity is created between two communication endpoints such as mobile devices. This Physically Unclonable Digital ID (PUDID) is created by injecting a data scrambling PUF device at the data origin point that corresponds to a unique and matching descrambler/hardware authentication at the receiving end. This device is designed using macroscopic, intentional anomalies, making them inexpensive to produce. PUDID is resistant to cryptanalysis due to the separation of the challenge response pair and a series of hash functions. PUDID is also unique in that by combining the PUF device identity with a dynamic human identity, we can create true two-factor authentication. We also propose an alternative solution that eliminates the need for a PUF mechanism altogether by combining tamper resistant capabilities with a series of hash functions. This tamper resistant device, referred to as a Quasi-PUDID (Q-PUDID), modifies input data, using a black-box mechanism, in an unpredictable way. By mimicking PUF attributes, Q-PUDID is able to avoid traditional PUF challenges thereby providing high-performing physical identity assurance with or without a low performing PUF mechanism. Three different application scenarios with mobile devices for PUDID and Q-PUDI- have been analyzed to show their unique advantages over traditional PUFs and outline the potential for placement in a host of applications.
Keywords: authorisation; cryptography; random number generation; PUF; Q-PUDID; center for strategic and international studies; clonable static information; cryptanalysis; descrambler-hardware authentication; device authentication; digital identity thefts; dynamic human identity; encryption keys; hash functions; physically unclonable digital ID; physically unclonable function; quasi-PUDID; random number generation; two-factor authentication; Authentication; Cryptography; Immune system; Optical imaging; Optical sensors; Servers; PUF; access control; authentication; biometrics; cloning; computer security; cyber security; digital signatures; identification of persons; identity management systems; mobile hardware security (ID#: 16-10879)


A. Al-Anwar, Y. Alkabani, M. W. El-Kharashi and H. Bedour, “Hardware Trojan Protection for Third Party IPs,” Digital System Design (DSD), 2013 Euromicro Conference on, Los Alamitos, CA, 2013, vol., no., pp. 662-665. doi:10.1109/DSD.2013.133
Abstract: Hardware Trojan detection is a very important topic especially as parts of critical systems which are designed and/or manufactured by untrusted third parties. Most of the current research concentrates on detecting Trojans at the testing phase by comparing the suspected circuit to a golden (trusted) one. However, these attempts do not work in the case of third party IPs, which are black boxes with no golden IPs to trust. In this work, we present novel methods for system protection that alleviate the need for a golden chip. Protection against injected Trojan is done using simple blockage method. We show the practicality of the introduced schemes by providing a proof of concept implementation of the proposed methodology on FPGA. We showed that the overhead is low enough in the simple blockage method. The delay overhead is negligible while the power overhead does not exceed 2%.
Keywords: field programmable gate arrays; logic design; trusted computing; FPGA; black boxes; critical systems; golden chip; hardware trojan protection; simple blockage method; system protection; third party IP; Benchmark testing; Cryptography; Delays; Hardware; IP networks; Standards; Trojan horses; backdoors; hardware; hardware attack; hardware trojan; security; third-party IP (ID#: 16-10880)


C. Wu and S. Marotta, “Framework for Assessing Cloud Trustworthiness,” Cloud Computing (CLOUD), 2013 IEEE Sixth International Conference on, Santa Clara, CA, 2013, vol., no., pp. 956-957. doi:10.1109/CLOUD.2013.76
Abstract: When applications or data reside in a public cloud, trustworthiness can be compromised due to lack of control over the underlying infrastructure. Most public cloud infrastructures cannot be instrumented or modified to independently verify data integrity. To support verifiable access to applications and data residing in cloud infrastructures, we are developing a framework that treats the cloud as a black box and assesses its trustworthiness from the trusted cloud client. Our solution generates and performs diagnostic tests to assess the trustworthiness of cloud-based applications. Diagnostic tests for data objects stored in the cloud are based on a separate cryptographic hash-based check that verifies their data integrity.
Keywords: cloud computing; cryptography; data integrity; program testing; trusted computing; black box; cloud trustworthiness; cloud-based applications; cryptographic hash-based check; data integrity; diagnostic tests; public cloud infrastructures; trusted cloud client; Cloud computing; Instruments; Monitoring; Optimization; Security; Testing; cloud computing; security; trustworthiness; data integrity (ID#: 16-10881)


K. Butterfield, H. Li, X. Zou and F. Li, “Enhancing and Implementing Fully Transparent Internet Voting,” Computer Communication and Networks (ICCCN), 2015 24th International Conference on, Las Vegas, NV, 2015, vol., no., pp. 1-6. doi:10.1109/ICCCN.2015.7288408
Abstract: Voting over the internet has been the focus of significant research with the potential to solve many problems. Current implementations typically suffer from a lack of transparency, where the connection between vote casting and result tallying is seen as a black box by voters. A new protocol was recently proposed that allows full transparency, never obfuscating any step of the process, and splits authority between mutually-constraining conflicting parties. Achieving such transparency brings with it challenging issues. In this paper we propose an efficient algorithm for generating unique, anonymous identifiers (voting locations) that is based on the Chinese Remainder Theorem, we extend the functionality of an election to allow for races with multiple winners, and we introduce a prototype of this voting system implemented as a multiplatform web application.
Keywords: Internet; Chinese remainder theorem; election functionality extension; multiplatform Web application; transparent Internet voting implementing; vote casting; Cryptography; Internet; Nominations and elections; Protocols; Prototypes; Synchronization (ID#: 16-10882)


A. Ahmad, M. Farooq and M. Amin, “SBoxScope: A Meta S-box Strength Evaluation Framework for Heterogeneous Confusion Boxes,” 2016 49th Hawaii International Conference on System Sciences (HICSS), Koloa, HI, USA, 2016, vol., no.,
pp. 5545-5553. doi:10.1109/HICSS.2016.685
Abstract: In cipher algorithms, both block or streaming, the most important non-linear component is a confusion box (commonly termed as s Substitution box or an S-box). The designers of cipher algorithms create an S-box on the basis of a unique formal model, as a result, its parameters, including its size, are different. Consequently, it becomes a daunting task for a cryptanalyst to conduct a comparative study to analyze, in a scientific yet unbiased manner, the cryptographic strength of these heterogeneous S-boxes. The major contribution of this paper is SBoxScope, a meta S-Box strength evaluation framework that enables designers and analysts to evaluate cryptographic strength of heterogeneous S-boxes. The framework consists of two layers: (1) White Box Layer analyzes the contents of an S-box and calculates 8 relevant parameters (5 core and 3 auxiliary) and then normalizes them to draw conclusions about the strength of an S-box, (2) Black Box Layer assumes that no knowledge is available about the contents of an S-box, rather, it gives a predefined input bit stream to each S-box and then applies NIST tests to measure 10 parameters. Finally, the two layer are augmented that empowers an analyst to make a decision about the strength of an S-box after analyzing 18 different parameters. In this paper, we have evaluated 9 S-boxes of five well known cipher algorithms: AES, MARS, Skipjack, Serpent and Twofish.
Keywords: Algorithm design and analysis; Ciphers; Computer architecture; Correlation; Mars; NIST; Cipher Algorithms; Cryptographic Strength; Cryptography (ID#: 16-10883)


K. M. Chung, H. Lin and R. Pass, “Constant-Round Concurrent Zero Knowledge from P-Certificates,” Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, Berkeley, CA, 2013, vol., no., pp. 50-59. doi:10.1109/FOCS.2013.14
Abstract: We present a constant-round concurrent zero-knowledge protocol for NP. Our protocol relies on the existence of families of collision-resistant hash functions, and a new, but in our eyes, natural complexity-theoretic assumption: the existence of P-certificates-that is, “succinct” non-interactive proofs/arguments for P. As far as we know, our results yield the first constant-round concurrent zero-knowledge protocol for NP with an explicit zero-knowledge simulator based on any assumption.
Keywords: computational complexity; concurrency theory; theorem proving; P-certificates; collision-resistant hash functions; constant-round concurrent zero-knowledge protocol; explicit zero-knowledge simulator; natural complexity-theoretic assumption; zero-knowledge interactive proofs; Awards activities; Complexity theory; Computational modeling; Concurrent computing; Polynomials; Protocols; Security; Concurrent Zero-Knowledge; Cryptography; Non-Black-Box Technique (ID#: 16-10884)


Qihui Zhang et al., “Optimization Design of a Low Power Asynchronous DES for Security Applications Based on Balsa and Synchronous Tools,” Electronics, Communications and Computers (CONIELECOMP), 2015 International Conference on, Cholula, 2015, vol., no., pp. 124-129. doi:10.1109/CONIELECOMP.2015.7086938
Abstract: DES has been widely used in current financial security application, but side-channel attacks are considered as serious threats to DES cryptographic algorithm. Asynchronous DES design will be a proper solution because of its natural properties. First, a low power asynchronous DES architecture and sub key generation architecture are proposed. Then, optimized Balsa implementation, GTECH-based implementation and black-box-based implementation are described to reduce area and power. Furthermore, a dual-rail implementation is carried out for future security applications and a Spartan-6 FPGA verification is checked before taping out. ASIC implementation results show that our proposed asynchronous DES architecture and black-box-based scheme can achieve about 20% lower power with 25% area increase of its synchronous equivalent, and its energy is only 8.2% and 27.3% of those reported in other papers, respectively. FPGA experimental results show that our proposed asynchronous DES exhibits an operation frequency of 196.2 MHz and costs only 4% slice LUTs. Moreover, it can be suitably integrated into contactless smart cards.
Keywords: application specific integrated circuits; cryptography; field programmable gate arrays; standards; ASIC implementation; Balsa implementation; DES cryptographic algorithm; GTECH-based implementation; Spartan-6 FPGA verification; asynchronous DES architecture; black-box-based implementation; data encryption standard; dual-rail implementation; frequency 196.2 MHz; low power asynchronous DES; security applications; slice LUT; sub key generation architecture; synchronous tools; Application specific integrated circuits; Computer architecture; Field programmable gate arrays; Hardware design languages; Libraries; Logic gates; Optimization; ASIC; Balsa properties; FPGA; asynchronous DES; dual-rail; low power; optimization schemes; security applications (ID#: 16-10885)


R. Cheng, F. Diao and F. Zhang, “On Obfuscating Set-Membership Predicate Functions,” Intelligent Networking and Collaborative Systems (INCoS), 2013 5th International Conference on, Xi’an, 2013, vol., no., pp. 304-308. doi:10.1109/INCoS.2013.54
Abstract: Obfuscation was first studied in computer programming field, which could be explained as a compiler that translates computer codes into an unintelligible form while preserving the original functionality. Since obfuscation for cryptographic purposes was raised out, several positive results have been presented in despite of the general impossibility. Secure obfuscation of point functions have been studied well and it was pointed out that secure composition of several point function obfuscation could realize the secure obfuscation of set-membership predicate function. However, secure composition of point function obfuscation was only proposed in one literature and the security was proved in Generic Group Model (GGM) under the definition of Virtual Grey Box-Obfuscation (VGB). In this paper we propose a new obfuscation construction of set-membership predicate functions under the standard definition of Virtual Black Box-Obfuscation (VBB). We utilize the vector space technique instead of obfuscation composition, and the security of obfuscation relies on an assumption which exists in standard model. Moreover, our obfuscation result of set-membership predicate functions can hide the real scale of the set and the obfuscation construction can be securely composed for different sets.
Keywords: cryptography; set theory; vectors; compiler; computer programming; cryptographic purposes; generic group model; obfuscation composition; obfuscation security; point function obfuscation; set-membership predicate functions; vector space technique; virtual black box-obfuscation; virtual grey box-obfuscation; Cryptography; Educational institutions; Equations; Mathematical model; Standards; Vectors; Privacy; secure obfuscation; set-membership predicate function; vector space (ID#: 16-10886)


G. S. Babil, O. Mehani, R. Boreli and M. A. Kaafar, “On the Effectiveness of Dynamic Taint Analysis for Protecting Against Private Information Leaks on Android-Based Devices,” Security and Cryptography (SECRYPT), 2013 International Conference on, Reykjavik, Iceland, 2013, vol., no., pp. 1-8. doi: (not provided)
Abstract: We investigate the limitations of using dynamic taint analysis for tracking privacy-sensitive information on Android-based mobile devices. Taint tracking keeps track of data as it propagates through variables, interprocess messages and files, by tagging them with taint marks. A popular taint-tracking system, TaintDroid, uses this approach in Android mobile applications to mark private information, such as device identifiers or user’s contacts details, and subsequently issue warnings when this information is misused (e.g., sent to an un-desired third party). We present a collection of attacks on Android-based taint tracking. Specifically, we apply generic classes of anti-taint methods in a mobile device environment to circumvent this security technique. We have implemented the presented techniques in an Android application, ScrubDroid. We successfully tested our app with the TaintDroid implementations for Android OS versions 2.3 to 4.1.1, both using the emulator and with real devices. Finally, we evaluate the success rate and time to complete of the presented attacks. We conclude that, although taint tracking may be a valuable tool for software developers, it will not effectively protect sensitive data from the black-box code of a motivated attacker applying any of the presented anti-taint tracking methods.
Keywords: Androids; Arrays; Humanoid robots; Malware; Mobile communication; Mobile handsets; Software; Android; Anti-Taint-Analysis; Anti-TaintDroid; Dynamic Taint Analysis; Malware; Privacy (ID#: 16-10887)


M. Kim and K. Y. Kim, “Data Forgery Detection for Vehicle Black Box,” Information and Communication Technology Convergence (ICTC), 2014 International Conference on, Busan, 2014, vol., no., pp. 636-637. doi:10.1109/ICTC.2014.6983237
Abstract: This paper presents a security scheme to detect the data forgery in the vehicle black box system. The proposed scheme uses chained hash and symmetric-key encryption to check whether the data is forged or modified. Experimental results show that the proposed scheme can find and notify the point of the falsification. Based on our experiment, we believe that the proposed scheme could be a practical solution to improve the reliability of the black box data.
Keywords: cryptography; data recording; driver information systems; road vehicles; chained hash encryption; data forgery detection; driving information; security scheme; symmetric-key encryption; vehicle black box system; Accidents; Encryption; Forgery; Reliability; Vehicles; Black Box; Event data recorder; information security (ID#: 16-10888)


R. Canetti, H. Lin and R. Pass, “From Unprovability to Environmentally Friendly Protocols,” Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, Berkeley, CA, 2013, vol., no., pp. 70-79. doi:10.1109/FOCS.2013.16
Abstract: An important security concern for crypto-graphic protocols is the extent to which they adversely affect the security of the systems in which they run. In particular, can we rule out the possibility that introducing a new protocol to a system might, as a “side effect”, break the security of unsuspecting protocols in that system? Universally Composable (UC) security rules out such adverse side effects. However, many functionalities of interest provably cannot be realized with UC security unless the protocol participants are willing to put some trust in external computational entities. We propose a notion of security that: (a) allows realizing practically any functionality by protocols in the plain model without putting trust in any external entity; (b) guarantees that secure protocols according to this notion have no adverse side-effects on existing protocols in the system — as long as the security of these existing protocols is proven via the traditional methodology of black box reduction to a game-based cryptographic hardness assumption with bounded number of rounds. Our security notion builds on the angel-based security notion of Prabhakaran and Sahai. A key part in our analysis is to come up with a CCA-secure commitment scheme that (a) cannot be proven secure via a black box reduction to a game-based assumption, but (b) can be proven secure using a non-black-box reduction. To the best of our knowledge, this is the first time that the interplay between black-box provability and unprovability is used to demonstrate security properties of protocols.
Keywords: cryptographic protocols; game theory; CCA-secure commitment scheme; UC security; angel-based security notion; black box reduction; black-box unprovability; chosen-commitment-attack secure commitment scheme; crypto-graphic protocols; environmentally friendly protocols; external computational entities; game-based cryptographic hardness assumption; plain model; protocol security properties; secure protocols; universally composable security; Awards activities; Cryptography; Educational institutions; Games; Polynomials; Protocols; Angel-Based Security; Black-Box Unprovability; Cryptography; Environmentally Friendliness (ID#: 16-10889)


C. Gentry, S. Halevi, M. Raykova and D. Wichs, “Outsourcing Private RAM Computation,” Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, Philadelphia, PA, 2014, vol., no., pp. 404-413. doi:10.1109/FOCS.2014.50
Abstract: We construct the first schemes that allow a client to privately outsource arbitrary program executions to a remote server while ensuring that: (I) the client’s work is small and essentially independent of the complexity of the computation being outsourced, and (II) the server’s work is only proportional to the run-time of the computation on a random access machine (RAM), rather than its potentially much larger circuit size. Furthermore, our solutions are non-interactive and have the structure of reusable garbled RAM programs, addressing an open question of Lu and Ostrovsky (Eurocrypt 2013). We also construct schemes for an augmented variant of the above scenario, where the client can initially outsource a large private and persistent database to the server, and later outsource arbitrary program executions with read/write access to this database. Our solutions are built from non-reusable garbled RAM in conjunction with new types of reusable garbled circuits that are more efficient than prior solutions but only satisfy weaker security. For the basic setting without a persistent database, we can instantiate the required type of reusable garbled circuits from indistinguishability obfuscation or from functional encryption for circuits as a black-box. For the more complex setting with a persistent database, we can instantiate the required type of reusable garbled circuits using stronger notions of obfuscation. Our basic solution also requires the client to perform a one-time pre-processing step to garble a program at the cost of its RAM run-time, and we can avoid this cost using stronger notions of obfuscation. It remains an open problem to instantiate these new types of reusable garbled circuits under weaker assumptions, possibly avoiding obfuscation altogether. We show several simple extensions of our results and techniques to achieve: efficiency proportional to the input-specific RAM run-time, verifiability of outsourced RAM computation, functional encryption for RAMs, and a candidate obfuscation for RAMs.
Keywords: cryptography; outsourcing; program compilers; software reusability; computation complexity; functional encryption; input-specific RAM run-time; nonreusable garbled RAM; one-time preprocessing step; outsourced RAM computation verifiability; private RAM computation outsourcing; private arbitrary program execution outsourcing; random access machine; read-write access; remote server; reusable garbled RAM programs; Complexity theory; Databases; Outsourcing; Protocols; Random access memory; Security; Servers; obfuscation; reusable garbled RAM; reusable garbled circuits (ID#: 16-10890)


F. Aarts, J. De Ruiter and E. Poll, “Formal Models of Bank Cards for Free,” Software Testing, Verification and Validation Workshops (ICSTW), 2013 IEEE Sixth International Conference on, Luxembourg, 2013, pp. 461-468. doi:10.1109/ICSTW.2013.60
Abstract: Learning techniques allow the automatic inference of the behaviour of a system as a finite state machine. We demonstrate that learning techniques can be used to extract such formal models from software on banking smartcards which, as most bank cards do, implement variants of the EMV protocol suite. Such automated reverse-engineering, which only observes the smartcard as a black box, takes little effort and is fast. The finite state machine models obtained provide a useful insight into decisions (or indeed mistakes) made in the design and implementation, and would be useful as part of security evaluations, not just for bank cards but for smartcard applications in general, as they can show unexpected additional functionality that is easily missed in conformance tests.
Keywords: banking; finite state machines; formal specification; formal verification; inference mechanisms; learning (artificial intelligence); reverse engineering; security of data; smart cards; EMV protocol suite; banking smart card; finite state machine; formal model; learning technique; security evaluation; smart card application; system behaviour inference; Credit cards; Cryptography; Learning automata; Protocols; Standards; Testing (ID#: 16-10891)


L. Chen, H. W. Lim and G. Yang, “Cross-Domain Password-Based Authenticated Key Exchange Revisited,” INFOCOM, 2013 Proceedings IEEE, Turin, 2013, vol., no., pp. 1052-1060. doi:10.1109/INFCOM.2013.6566895
Abstract: We revisit the problem of cross-domain secure communication between two users belonging to different security domains within an open and distributed environment. Existing approaches presuppose that either the users are in possession of public key certificates issued by a trusted certificate authority (CA), or the associated domain authentication servers share a long-term secret key. In this paper, we propose a four-party password-based authenticated key exchange (4PAKE) protocol that takes a different approach from previous work. The users are not required to have public key certificates, but they simply reuse their login passwords they share with their respective domain authentication servers. On the other hand, the authentication servers, assumed to be part of a standard PKI, act as ephemeral CAs that “certify” some key materials that the users can subsequently exchange and agree on a session key. Moreover, we adopt a compositional approach. That is, by treating any secure two-party password-based key exchange protocol and two-party asymmetric-key based key exchange protocol as black boxes, we combine them to obtain a generic and provably secure 4PAKE protocol.
Keywords: cryptographic protocols; public key cryptography; telecommunication security; cross-domain password-based authenticated key exchange; cross-domain secure communication; domain authentication servers; four-party password-based authenticated key exchange protocol; long-term secret key; public key certificates; trusted certificate; two-party asymmetric-key based key exchange protocol; two-party password-based key exchange protocol; Authentication; Electronic mail; Materials; Protocols; Public key; Servers; Password-based protocol; client-to-client; cross-domain; key exchange (ID#: 16-10892)


N. Bitansky, O. Paneth and A. Rosen, “On the Cryptographic Hardness of Finding a Nash Equilibrium,” Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, Berkeley, CA, 2015, vol., no., pp. 1480-1498. doi:10.1109/FOCS.2015.94
Abstract: We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which finding Nash equilibrium is complete. Previous proposals for basing PPAD-hardness on program obfuscation considered a strong “virtual black-box” notion that is subject to severe limitations and is unlikely to be realizable for the programs in question. In contrast, for indistinguishability obfuscation no such limitations are known, and recently, several candidate constructions of indistinguishability obfuscation were suggested based on different hardness assumptions on multilinear maps. Our result provides further evidence of the intractability of finding a Nash equilibrium, one that is extrinsic to the evidence presented so far.
Keywords: computational complexity; cryptography; game theory; PPAD complexity class; complete Nash equilibrium; cryptographic hardness; hard computational problem; hard-Nash equilibrium; indistinguishability obfuscation; multilinear maps; one-way functions; subexponential hardness; Complexity theory; Computer science; Cryptography; Games; Search problems; nash equilibrium; obfuscation (ID#: 16-10893)


Articles listed on these pages have been found on publicly available internet pages and are cited with links to those pages. Some of the information included herein has been reprinted with permission from the authors or data repositories. Direct any requests via Email to for removal of the links or modifications to specific citations. Please include the ID# of the specific citation in your correspondence.