Colquhoun's Crypto Corner: a sample

In early 2012 I started to write a regular column in the ASTC's newsletter, now known as Context. Here, by way of a sample, is the first, introductory, one (PDF, 183 kB).

Other columns have looked at

• Cryptographic terminology and phone hacking
• An important security breach and the Australian Government Information Security Manual
• Encryption and how Julius Caesar did it
• Security scams and non-scams and, again, the Australian Government Information Security Manual
• Cloud storage
• PDF encryption
• How long should your password be?
• Approving documents, and the Australian Government Information Security Manual again.
• Digital signatures

Cryptography

Here are some PDFs which have more than one user password!

These files use native PDF 40-bit (RC4) encryption. (Which is now obsolete, but useful for this project.)

The passwords are all digits, but are strings of 13 characters.

This file has passwords 1099511627778 (which is the originally set-up password; note that it is 2⁴⁰+2) and 0337781105149.

This file has passwords 1099511627785 (2⁴⁰+9) and 0825824783350.

This file has four passwords! 1099511627786 (2⁴⁰+10), 0234781044726, 0242169810842 and 0456224015647.

This file has passwords 1099511627787 (2⁴⁰+11), 0228713541285 and 0542802457664.

This file has passwords 1099511627788 (2⁴⁰+12) and 0311402722922.

This file has passwords 1099511627790 (2⁴⁰+14), 0194344002569 and 0548392510191.

This file has passwords 1099511627791 (2⁴⁰+15), 0344644907768 and 0983900906236.

Method:

1. Create a PDF with 'nominal' password 1099511627776 (that is, 2⁴⁰).
2. Search for a colliding password in the range [0,1099511627775].
3. If no success, create a new PDF with 'nominal' password 1099511627777 and search again.
4. If no success, increment the nominal password again and keep trying.

This yielded the collisions above.

So this is not an exhaustive search for password collisions; it just searches a space of size 2⁴⁰.

How these collisions should be distributed

Acrobat creates the key from the password by applying RC4 once.

Suppose that RC4 generates random output.

What does it mean?

More to come...

Back to aryl's Home Page.