Malicious Cryptography: Exposing Cryptovirology

Cover......Page 1
Contents......Page 10
Foreword......Page 16
Acknowledgments......Page 22
Introduction......Page 24
1 Through Hacker\'s Eyes......Page 28
2 Cryptovirology......Page 60
3 Tools for Security and Insecurity......Page 78
3.1 Sources of Entropy......Page 80
3.2 Entropy Extraction via Hashing......Page 81
3.3.1 Von Neumann\'s Coin Flipping Algorithm......Page 84
3.3.2 Iterating Neumann\'s Algorithm......Page 86
3.3.3 Heuristic Bias Matching......Page 87
3.4 Combining Weak Sources of Entropy......Page 89
3.5.1 Heuristic Pseudorandom Number Generation......Page 93
3.5.2 PRNGs Based on Reduction Arguments......Page 94
3.6 Uniform Sampling......Page 95
3.7.1 Shuffling Cards by Repeated Sampling......Page 98
3.7.2 Shuffling Cards Using Trotter-Johnson......Page 100
3.8 Sound Approach to Random Number Generation and Use......Page 103
3.9 RNGs Are the Beating Heart of System Security......Page 104
3.10.1 Strong Crypto Yields Strong Cryptoviruses......Page 105
3.10.2 Mix Networks and Cryptovirus Extortion......Page 107
3.11 Anonymizing Program Propagation......Page 112
4.1 Anonymity in a Digital Age......Page 116
4.1.2 Electronic Money and Anonymous Payments......Page 117
4.1.3 Anonymous Assassination Lotteries......Page 119
4.1.4 Kidnapping and Perfect Crimes......Page 120
4.1.5 Conducting Criminal Operations with Mixes......Page 121
4.2.1 Password Snatching and Security by Obscurity......Page 124
4.2.2 Solving the Problem Using Cryptovirology......Page 125
4.2.3 Zero-Knowledge Proofs to the Rescue......Page 127
4.2.4 Improving the Attack Using ElGamal......Page 128
5 Cryptocounters......Page 130
5.1 Overview of Cryptocounters......Page 131
5.2.1 A Simple Counter Based on ElGamal......Page 132
5.2.2 Drawback to the ElGamal Solution......Page 133
5.2.3 Cryptocounter Based on Squaring......Page 134
5.2.4 The Paillier Encryption Algorithm......Page 135
5.3 Other Approaches to Cryptocounters......Page 138
6 Computationally Secure Information Stealing......Page 140
6.1 Using Viruses to Steal Information......Page 141
6.2 Private Information Retrieval......Page 142
6.2.1 PIR Based on the Phi-Hiding Problem......Page 144
6.2.2 Security of the Phi-Hiding PIR......Page 147
6.3 A Variant of the Phi-Hiding Scheme......Page 149
6.4 Tagged Private Information Retrieval......Page 153
6.5 Secure Information Stealing Malware......Page 158
6.6 Deniable Password Snatching Based on Phi-Hiding......Page 159
6.6.1 Improved Password-Snatching Algorithm......Page 160
6.6.2 Questionable Encryptions......Page 161
6.6.3 Deniable Encryptions......Page 166
6.7 Malware Loaders......Page 167
6.8 Cryptographic Computing......Page 168
7 Non-Zero Sum Games and Survivable Malware......Page 174
7.1 Survivable Malware......Page 175
7.2 Elements of Game Theory......Page 177
7.3 Attacking a Brokerage Firm......Page 178
7.3.1 Assumptions for the Attack......Page 179
7.3.2 The Distributed Cryptoviral Attack......Page 180
7.3.3 Security of the Attack......Page 185
7.3.4 Utility of the Attack......Page 186
7.4.1 Key Search via Facehuggers......Page 188
7.5 Future Possibilities......Page 194
8.1 Undecidability of Virus Detection......Page 198
8.2 Virus Identification and Obfuscation......Page 199
8.2.1 Virus String Matching......Page 200
8.2.2 Polymorphic Viruses......Page 203
8.3.1 Detecting Code Abnormalities......Page 209
8.3.2 Detecting Abnormal Program Behavior......Page 210
8.3.3 Detecting Cryptographic Code......Page 218
8.4.1 Integrity Self-Checks......Page 224
8.4.2 Program Inoculation......Page 225
8.4.3 Kernel Based Signature Verification......Page 226
9 The Nature of Trojan Horses......Page 228
9.2 Salami Slicing Attacks......Page 229
9.3 Thompson\'s Password Snatcher......Page 230
9.4 The Subtle Nature of Trojan Horses......Page 233
9.4.2 RNG Biasing Trojan Horse......Page 235
10 Subliminal Channels......Page 238
10.1 Brief History of Subliminal Channels......Page 239
10.2 The Difference Between a Subliminal and a Covert Channel......Page 241
10.3 The Prisoner\'s Problem of Gustavus Simmons......Page 242
10.4 Subliminal Channels New and Old......Page 243
10.4.1 The Legendre Channel of Gus Simmons......Page 244
10.4.2 The Oracle Channel......Page 247
10.4.3 Subliminal Card Marking......Page 249
10.4.4 The Newton Channel......Page 250
10.4.5 Subliminal Channel in Composites......Page 251
10.5 The Impact of Subliminal Channels on Key Escrow......Page 253
11 SETUP Attack on Factoring Based Key Generation......Page 256
11.1 Honest Composite Key Generation......Page 258
11.2 Weak Backdoor Attacks on Composite Key Generation......Page 259
11.2.1 Using a Fixed Prime......Page 260
11.2.2 Using a Pseudorandom Function......Page 261
11.2.3 Using a Pseudorandom Generator......Page 263
11.3 Probabilistic Bias Removal Method......Page 266
11.4 Secretly Embedded Trapdoors......Page 268
11.5 Key Generation SETUP Attack......Page 271
11.6.1 Indistinguishability of Outputs......Page 276
11.6.2 Confidentiality of Outputs......Page 279
11.7 Detecting the Attack in Code Reviews......Page 283
11.8 Countering the SETUP Attack......Page 286
11.9 Thinking Outside the Box......Page 288
11.10 The Isaac Newton Institute Lecture......Page 289
12 SETUP Attacks on Discrete-Log Cryptosystems......Page 292
12.1 The Discrete-Log SETUP Primitive......Page 293
12.2 Diffie-Hellman SETUP Attack......Page 295
12.3.1 Indistinguishability of Outputs......Page 297
12.3.2 Confidentiality of Outputs......Page 298
12.4 Intuition Behind the Attack......Page 302
12.5 Kleptogram Attack Methodology......Page 303
12.6.1 ElGamal PKCS SETUP Attack......Page 304
12.6.2 Cramer-Shoup PKCS SETUP Attack......Page 306
12.7 SETUP Attacks on Digital Signature Algorithms......Page 307
12.7.1 SETUP in the ElGamal Signature Algorithm......Page 308
12.7.2 SETUP in the Pointcheval-Stern Algorithm......Page 309
12.7.3 SETUP in DSA......Page 310
12.7.4 SETUP in the Schnorr Signature Algorithm......Page 311
12.8 Rogue Use of DSA for Encryption......Page 312
12.9 Other Work in Kleptography......Page 313
12.10 Should You Trust Your Smart Card?......Page 315
A.1 Origins of Malicious Software......Page 322
A.2 Trojans, Viruses, and Worms: What Is the Difference?......Page 324
A.3 A Simple DOS COM Infector......Page 326
A.4 Viruses Don\'t Have to Gain Control Before the Host......Page 330
B.1 Notation Used Throughout the Book......Page 334
B.2 Basic Facts from Number Theory and Algorithmics......Page 336
B.3 Intractability: Malware\'s Biggest Ally......Page 339
B.3.1 The Factoring Problem......Page 340
B.3.3 The Composite Residuosity Problem......Page 341
B.3.6 The Phi-Hiding Problem......Page 342
B.3.7 The Phi-Sampling Problem......Page 344
B.3.10 The Decision Diffie-Hellman Problem......Page 345
B.4 Random Oracles and Functions......Page 346
C.1 Overview of Cryptography......Page 348
C.1.1 Classical Cryptography......Page 349
C.1.2 The Diffie-Hellman Key Exchange......Page 351
C.1.3 Public Key Cryptography......Page 352
C.1.4 Attacks on Cryptosystems......Page 353
C.1.5 The Rabin Encryption Algorithm......Page 357
C.1.6 The Rabin Signature Algorithm......Page 358
C.1.7 The RSA Encryption Algorithm......Page 359
C.1.8 The RSA Signature Algorithm......Page 361
C.1.9 The Goldwasser-Micali Algorithm......Page 362
C.1.10 Public Key Infrastructures......Page 363
C.2 Discrete-Log Based Cryptosystems......Page 364
C.2.2 Security of ElGamal......Page 365
C.2.3 The Cramer-Shoup Encryption Algorithm......Page 367
C.2.4 The ElGamal Signature Algorithm......Page 369
C.2.5 The Pointcheval-Stern Signature Algorithm......Page 370
C.2.6 The Schnorr Signature Algorithm......Page 371
C.2.7 The Digital Signature Algorithm (DSA)......Page 372
Glossary......Page 374
References......Page 384
Index......Page 414