The Long-Short-Key Primitive and Its Applications to Key Security
Cryptographic insecurities on open systems due to software vulnerabilities lead to the need for a novel approach to protect keys. This approach involves a long-short-key primitive, aiming to safeguard secret keys effectively. The implementation and various applications of this method are discussed in detail, emphasizing the significance of key security in diverse contexts like DRM, full disk encryption, and authentication.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
The Long-Short-Key Primitive and Its Applications to Key Security Matthew Cary Google Mariusz H. Jakubowski Ramarathnam Venkatesan Microsoft Research Matthias Jacob Nokia International Workshop on Security: IWSEC 08 Kagawa, Japan November 25-27, 2008
Introduction Cryptographic (in)security on open PCs Software susceptible to observation and modification Secret data visible at runtime in memory Key-secrecy assumption violated Some current contexts: DRM (secured audio, video, e-books) Full disk encryption (BitLocker) Authentication (passwords, biometrics) 11/27/08 2
Introduction Traditional approaches may not suffice: Obfuscation Tamper-resistance Goals of our work: Propose a novel approach to protect keys. Present several applications. Report on an implementation. 11/27/08 3
Overview Protection of cryptographic keys on open systems Introduction Background The long-short-key primitive Implementation Applications Conclusion 11/27/08 4
Software Protection Obfuscation Code difficult to understand and modify Many ad hoc techniques in popular use Theoretical results often negative White-boxing Hiding cryptographic keys (e.g., AES, RSA, RC4) Each key K transformed into code that encrypts or decrypts without revealing K. K should be difficult to extract from code. Security often not guaranteed Typically no practical security proofs Many schemes released, broken and fixed 11/27/08 5
Other Related Areas Bounded-storage models Maurer, Dziembowski et al. Forward-secure storage Large ciphertexts Partial ciphertext leakage does not reveal any plaintext, even with correct key. Intrusion resilience via bounded storage Large keys Partial key leakage does not facilitate decryption. Dynamic key generation and refresh 11/27/08 6
Overview Protection of cryptographic keys on open systems Introduction Background The long-short-key primitive Implementation Applications Conclusion 11/27/08 7
Long-Short-Key Primitive An alternative approach to key hiding Goal: Protect a secret key K. Basic approach: L = key_expand(K) EK,L(P) = C DK,L(C) = P Privately: Encrypt or decrypt with short key K. Publicly: Encrypt or decrypt with a long key L derived from K. 11/27/08 8
Long-Short-Key Security L = key_expand(K) EK,L(P) = C DK,L(C) = P Security model: System is fully open to inspection and modification. Adversary can access only L, not K. Kshould be hard to obtain from L. Desired (provable) security property: Minimum size of any hack is O(|L|). Forces attackers to redistribute large volume of key material. 11/27/08 9
Long-Short-Key Security L = key_expand(K) EK,L(P) = C DK,L(C) = P Implementation of key_expand(K) Secure pseudorandom generator Stream cipher (e.g., RC4 or a random-access cipher) This enforces the security property (minimum code size needed to implement encryption and decryption if K is not available). 11/27/08 10
Using the Long Key Let long key L = (X1, X2, , XN). Treat blocks X1, X2, , XN as cipher keys. Use a subset S of (X1, X2, , XN) as a sequence of keys for cryptographic operations. Modes of operation Sequential: Counter-based: Selective: S = Xi, Xi+1, S = XE(i), XE(i+1), S = XE(i), XC[0], XC[1], i = IV or initial counter, E(i) = encryption of i, C[k] = ciphertext block k (mod N) 11/27/08 11
Modes of Operation Methods of choosing subsets of long key for encryption and decryption Sequential S = Xi, Xi+1, Consecutive sequence of long-key blocks used as keys Simplest method with best performance Counter-based S = XE(i), XE(i+1), Randomized sequence of blocks Better variability of block selection Selective S = XE(i), XC[0], XC[1], Randomized and ciphertext-dependent sequence of blocks Most variability and unpredictability of block selection i = IV or initial counter, E(i) = encryption of i, C[k] = ciphertext block k (mod N) 11/27/08 12
Overview Protection of cryptographic keys on open systems Introduction Background The long-short-key primitive Implementation Applications Conclusion 11/27/08 13
Implementation AES-based framework Blocks of long key serve as distinct AES keys. Each key generates an instance of AES code. AES instances are merged and interleaved. Individualization and obfuscation Injection of chaff code Conversion of operations to table lookups Instruction interleaving Temporary corruption and restoration of data 11/27/08 14
Iterated Protection A framework for design, implementation and analysis of obfuscation methods Obfuscation operators are applied repeatedly over already obfuscated code. Interaction among operators leads to complex (emergent) code behavior and structure. Whole greater than the sum of its parts Security bootstrapped even via simple iterated primitives Inspired by cellular automata and rounds in cryptography Methodology may offer hope for security analysis. Metrics to estimate complexity of breaking Foundation for analysis of practical obfuscation methods Just one element to aid with comprehensive approaches 11/27/08 15
An Analogy: Iterated Translation Weakly obfuscating transformations that create complexity when iterated: Original: Code-obfuscation and tamper-resistance technologies aim to protect software against reverse engineering and hacking. Such methods include code-integrity verification, control-flow obfuscation, data encoding, anti- debugging, and many others. This technology is useful for applications such as content protection and Digital Rights Management, where code must execute as intended in order to enforce anti-piracy measures. Software protection is also helpful against viruses, worms, trojans, rootkits, and malicious code in general. English German French Spanish English Chinese English (via Babel Fish): Causes to change the dark code and the payment technology resistance cares for to protect r3etechnique and the Zerhacken program computer science opposition. Such method including code data fullness reconsideraci3on, Steuerung-fliessen changes darkly, compiles the statute book, AntiAuspruefen and other people. This technology is the useful legal management the protection which likely satisfies for the application and, in the code numeral the application must, expect there, imposes the antipiraterie set. The computer science program protection is the very useful opposition virus, the endless screw, Turlogh , rootkits and code boeswilligen in brief to general. English German English German English German English: If you code Kollusion and resistance technologies supplying, the goal away away of protecting for of of software from back technology and the Zerhacken. Such methods close completeness of the code test, taxliquid the Kollusion, the data coding out and anti-examining and that differently the many. This technology is for applications like content protection and must the right management, which is useful, the code digitally inside accomplish, for Piraterie mass anti forces there been supposed. Software protection is useful generally also against viruses, continuous screws, trojans, root installation of sentences and bad-ready code. 11/27/08 16
Example Protection Operators Complexity derived from iteration and recombination Oblivious hashing Injection of code to perform integrity checks of execution Hash updates after state changes (e.g., assignments and branches) Periodic checks for hash correctness First hashing round verifies execution of target code. Each subsequent round verifies execution of all previous rounds (along with target code). INITIALIZE_HASH(hash1); int x = 123; UPDATE_HASH(hash1, x); int x = 123; if (GetUserInput() > 10) { UPDATE_HASH(hash1, BRANCH_ID_1); x = x + 1; UPDATE_HASH(hash1, x); } else { UPDATE_HASH(hash1, BRANCH_ID_2); printf("Hello\n"); } if (GetUserInput() > 10) { x = x + 1; } else { printf("Hello\n"); } VERIFY_HASH(hash1); 11/27/08 17
Example Protection Operators Two iterated rounds of oblivious hashing INITIALIZE_HASH(hash1); INITIALIZE_HASH(hash2); int x = 123; UPDATE_HASH(hash1, x); UPDATE_HASH(hash2, x); UPDATE_HASH(hash2, hash1); INITIALIZE_HASH(hash1); int x = 123; UPDATE_HASH(hash1, x); if (GetUserInput() > 10) { UPDATE_HASH(hash1, BRANCH_ID_1); UPDATE_HASH(hash2, BRANCH_ID_1); UPDATE_HASH(hash2, hash1); x = x + 1; UPDATE_HASH(hash1, x); UPDATE_HASH(hash2, x); UPDATE_HASH(hash2, hash1); } else { UPDATE_HASH(hash1, BRANCH_ID_2); UPDATE_HASH(hash2, BRANCH_ID_2); UPDATE_HASH(hash2, hash1); printf("Hello\n"); } int x = 123; if (GetUserInput() > 10) { UPDATE_HASH(hash1, BRANCH_ID_1); x = x + 1; UPDATE_HASH(hash1, x); } else { UPDATE_HASH(hash1, BRANCH_ID_2); printf("Hello\n"); } if (GetUserInput() > 10) { x = x + 1; } else { printf("Hello\n"); } VERIFY_HASH(hash1); VERIFY_HASH(hash1); VERIFY_HASH(hash2); 11/27/08 18
Example Protection Operators Complexity derived from iteration and recombination Pointer conversion Conversion of variable references to be performed via pointers Addition of arbitrary layers of indirection int * ptr_x_2; int ** ptr_ptr_x_0_1; int * ptr_x_0; int x; ptr_ptr_x_0_1 = &ptr_x_0; ptr_x_2 = &x; *(int **) ptr_ptr_x_0_1 = ptr_x_2; unsigned int tmp_151 = (* (unsigned int (__stdcall *)()) &GetTickCount)(); int tmp_152 = (int) tmp_151; int * tmp_ptr_159 = * (int **) ptr_ptr_x_0_1; * (int *) tmp_ptr_159 = tmp_152; char * tmp_ptr_154 = (char *) "%d\n"; int * tmp_ptr_160 = * (int **) ptr_ptr_x_0_1; printf(tmp_ptr_154, * (int *) tmp_ptr_160); int * ptr_x_0; int x; ptr_x_0 = &x; unsigned int tmp_151 = (* (unsigned int (__stdcall *)()) &GetTickCount)(); int tmp_152 = (int) tmp_151; *(int *) ptr_x_0 = tmp_152; char * tmp_ptr_154 = (char *) "%d\n"; printf(tmp_ptr_154, * (int *) ptr_x_0); int x = GetTickCount(); printf("%d\n", x); Chaff-code injection Superdiversification (peephole instruction replacement) 11/27/08 19
Performance Number of rounds: A security parameter for each cipher-code instance. Illustrative figures: AES: 200 cycles/byte RSA: 2000 cycles/byte AES-LSK: 1500 cycles/byte 11/27/08 20
Overview Protection of cryptographic keys on open systems Introduction Background The long-short-key primitive Implementation Applications Conclusion 11/27/08 21
Applications Block-cipher security Long-key size may be arbitrary (KB, GB, ) Complicates remote-timing attacks Helps with white-boxing DRM No short key to extract and reuse ( type in ) Different content may use different key material 11/27/08 22
More Applications Software smartcards Short key in secure hardware smartcard Long key on software smartcard simulator Challenge-response authentication Short key on server Long key on client Challenges that use different parts of long key 11/27/08 23
Conclusion Contributions Novel primitive for key hiding and white-boxing Provable security metric (key length) Implementation with additional techniques Future work Other provable security metrics for key protection Analysis of iterated protection 11/27/08 24
