Channels ▼
RSS

Crypto Challenge Extended, Prize Increases


Crypto Challenge Extended, Reward Increases

Last year I conducted a contest to test the strength of an encryption utility, BCRP.EXE, offered a cash reward for any persons able to break the encryption. By the contest's deadline, no winning entries had been sumitted, so I've increased the prize. I have encrypted a test file, TEST6.DAT, and I issue this challenge: $4,000 (U.S.) will be awarded to the first party to submit proof of decrypting TEST6.DAT before August 31, 2001. The caveat for submissions, however, is that the persons who crack the code must prove that it can be broken by computer, and not by accidental "discovery" of the original text or passwords. Please review the complete list of rules and submission procedures included in the zip file before sending in your entry.

While further researching the bit-shuffling methods I employ in this code, particularly examining Terry Ritter's papers on transposition ciphers and Donald Knuth's treatises on randomization methods, I asked a number of leading experts in the field what type of attacks would have the best chance of success against this code. They suggested allowing chosen plaintext attacks, where the attacker sends me any number of their own plaintext files, I encrypt them with the same key as the original TEST6.DAT test file, and then I send the encrypted text files back to them for their examination.

Because of the limitations of e-mail volume on my server, I request that each user who wants to conduct a plaintext challenge limit their plain-text files to no more than 1 MB each, since the encrypted files generally won't be compressible with a "zip" utility. Note that because the Random Number Generator used in this code has a period of only 32,768 (addressing 32K bits, or 4 KB), and the maximum block size shuffled at one time is only 1,516 bits (189 bytes), files sizes larger than 100 KB or so are probably redundant.

Creating BCRP

The BCRP encryption program originated in early 1996 as a simple password "scrambler", upon the request of a person who needed same for a computer strategy/simulation game. Over the course of a few days, it evolved into the code presented here.

A few months after that I subscribed to the most well-known crypto forum on the Internet, to learn more about classic as well as state-of-the-art cryptographic and cryptologic methods. What came as a total surprise was the realization that state-of-the-art cryptography, in spite of advances such as "public key" ciphering, was still stuck in the 1940s mindset of bit changing, character substitution, and so on.

As I began to think about what I believed would be the most ideal (and possibly the most secure) encryption method, I though of a box full of letters and numbers such as A, B, C, 1, 2, 3, etc. wherein each letter and digit, and various punctuation characters, were somehow cut out of their original document one by one, and thrown into the box which then would be shaken to redistribute the characters as randomly as possible.

The problem with this was that you could not recover the original text from the box of characters, since it would then be possible to make up any message text from the more-or-less random assortment of characters in the box, rather than find the specific text of the original message.

It then occurred to me that you would not have to have the more-or-less infinite randomness of the box of characters, as long as you could have the flexibility to increase the randomness of a given crypto process to the point where an opponent could neither effect a brute-force decoding of your encrypted text (by checking every possible password value), nor be able to find a shortcut way to decipher your text through the use of advanced cryptanalysis.

At that point, I received numerous suggestions, criticisms and other ideas from persons on the Internet crypto forum, and I began working on the README.FAQ document, which compares the features of this code to major known cryptographic techniques, as well as known weaknesses in the various methods of encrypting text.

Putting BCRP to the Test

As it turns out, no amount of theory will make people feel safe in using an "uncertified" encryption program to protect their valuable secrets, whether routine competitive corporate strategies or production formulas, specialized scientific knowledge, software routines, or sensitive political information.

The most universally accepted method of introducing a new encryption program is to offer a reward to anyone who can decrypt a particular encoded text file, so I put together this system of files and documents and the $4,000 offer.

Notes

BCRP.EXE was compiled with MS-QuickBasic's v4.5 DOS compiler, and was linked with the QuickBasic linker. No effort has been made to optimize the current program, whether through improvements in "bit-shifting" technique, or through the use of fast loop-counting methods.

Encrypting the TEST5.DAT File

The TEST6.DAT file was encrypted with the BCRP.EXE program with two steps of processing, using the DOS command line as follows:

Step 1: BCRP TEST6.DAT /P
(pad 7-bit data with enough 8th bits to make the number of 0-bits and 1-bits in the result file as equal as possible).

Step 2: BCRP TEST6.DAT /E n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12
(n1, n2, n3, etc. = passwords, all numeric)

Decrypting the TEST6.DAT file

Reverse the encryption process as follows:

Step 1: BCRP TEST6.DAT /D n12 n11 n10 n9 n8 n7 n6 n5 n4 n3 n2 n1
(Note that the passwords are entered in reverse order, from 12 to 1 above, i.e. last encoded, first decoded)

Step 2: BCRP TEST6.DAT /U (unpad the 8th bit from the text).

Note that all of the programs in this package are MS-DOS programs, and should work with any PC-compatible computer that runs MS-DOS, Windows 95, Windows 98, and Windows NT. On Windows operating systems, you will have to get to your MS-DOS command line to run the programs since Windows' RUN option on the START menu will not set the current working directory properly.

Also, the BCRP.EXE program was compiled with the MS-QuickBasic v4.5 DOS compiler, dated Sep. 28, 1988.

Refer to the README.FAQ file for a technical discussion of the purpose and scope of this software and why a person might want to use this software in place of a more well-known encryptor.

Crypto Caveats

Although it is probably not possible in the real world to obtain 100 percent perfect security through encryption, these are the steps that I would try to implement as much as possible in my encryption processing:

a. Place your computer in a fully lead-shielded room, or barring that, have your computer shielded according to government specifications for secure work, or, place several radiation-noisy devices (radios, etc.) around the computer to try to mask the computer's emissions.

b. Never, ever write plain text to the computer's internal fixed disk.

Write plain text to a floppy diskette, and, never, ever use a word processor that writes temporary files to your internal fixed disk.

c. Don't store passwords on the internal disk, or barring that, secure the list of passwords by encrypting it with passwords you have only in memory, and never send passwords electronically unless encrypted the same way, to be decrypted by persons who share the same memory-only passwords with you, and who obtained those from you in person.

Contest Rules and Licensing

1. The person possessing these programs (the "user") may use them as is,
   or make any necessary changes to the source code, and then recompile
   them to put the new code changes into effect.  The user may also use
   parts of the source code in the user's own software whether personal
   or corporate, as long as the user:

   a. Does not use the entire (or nearly so) source code as is so that
      the user's resulting product is fundamentally the same as these
      programs, albeit with a possibly different "look and feel".

   b. Does not redistribute these programs and/or source code unless
      the user distributes the complete original set of files intact
      and without modification in one directory (i.e., 'CRYP'), and
      any additional and/or modified files in a separate directory.

2. Claims for the award given for decrypting the TEST6.DAT file:

   a. The sole purpose of the $4,000 (U.S.) award is to prove whether
      or not the TEST6.DAT file can be decrypted cryptologically (i.e.
      not through spying, or "accidental" discovery of the passwords
      or plain text).  To that end, a claimant must demonstrate the
      cryptologic method(s) used to decrypt the TEST6.DAT file.

      Any claim of success using the exhaustive search method cannot
      be validated, since the number of attempts required to decrypt
      TEST6.DAT (with 180 bits of "keyspace") would be approximately
      1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
      which is beyond the capabilities of all the world's computers
      (including Quantum** computers) for the next century or so.

    **See <a href="#FAQ">README.FAQ</a> for an explanation.  Since BCRP does not use
      mathematical shortcuts such as prime numbers, discrete logs,
      and so on to make "keys", BCRP can increase the security by
      simply incrementing the number of encryption layers with no
      upper limit.

      Non-civilian agencies wishing to claim the award, but who
      cannot reveal their decryption method for whatever reason,
      may be granted an exception, but only if it can be proven
      that their decryption does not involve the "accidental"
      discoveries as described above.  Decryption of a second
      test file, for which the passkeys could not possibly be
      known, should satisfy that condition.

   b. All claims must be submitted by postal mail, and must be
      postmarked on or before August 31, 2001.

   c. All claims must be accompanied by the plain text rendering of
      the TEST6.DAT file which was supplied in the original package.

   d. Any person who requests the ability to decrypt the TEST6.DAT
      file with their own MS-DOS/Windows PC, to assure themselves
      that the BCRP.EXE program works as represented here will be
      given the passwords to do so after Sep. 15, 2001. This will
      allow enough time for last-minute entries to be processed.

      For maximum assurance that the BCRP.EXE program was the actual
      compiled BCRP.BAS source code (see the README.2ND file) and that
      no tricks, traps, or other concealed artifacts were utilized to
      encrypt the TEST6.DAT file, the user should obtain a copy of the
      MS-QuickBasic v4.5 compiler dated Sep. 28, 1988, then recompile
      the source code themselves using the '/Ah' and '/O' switches.

   e. Only one award will be made, unless there are ties on the
      earliest submittal, in which case the award will be split
      evenly between the successful claimants.

   f. Any person who successfully decrypts the TEST6.DAT file, but
      who does not get the award due to an earlier and successful
      submittal, may request proof of that award by postal mail.

WARNING(!) Encryption changes the contents of a file, and if you cannot perform the decryption process properly including the use of keys/passwords, you won't be able to recover the file at all.

Normally, before making changes to any file you are advised to make a backup copy of the file, but since the purpose of encryption is to render the file unreadable or unusable, to have a working backup copy of the file on the same computer, or to have a copy in the same area in which the computer is located, would not suit the primary purpose of encryption.

WARNING(!) The current version of this program uses the DOS filename (the name of the file to be encrypted) to modify the pass- key number, which in turn determines the first block size for moving the bits from old to new positions within that block and each subsequent block. Therefore, do NOT change the filename in any way after encryption. Note also that certain Windows filenames (i.e., "long" filenames) may be represented by shorter DOS filenames in DOS windows, with characters such as '~1', '~2' etc. as part of the shorter DOS filename. THESE '~1', '~2', ETC. CHARACTERS (AS WELL AS OTHER SUBSTITUTED CHARACTERS) CAN CHANGE AUTOMATICALLY IF SUCH A FILE IS MOVED TO ANOTHER DISK DRIVE, OR ANOTHER DIRECTORY ON THE SAME DRIVE. For this reason, I recommend that you do NOT encrypt files with "long" filenames using the current version of this program.

This filename-dependent feature was added to the current version of this program to make the program resistant to "plain text attacks", so that if an attacker obtains one of your encrypted files, and also manages to find the un- encrypted text for that same file, they will not be able to decipher all of your encrypted files which were coded with the same passkeys by simply "combing" the encrypted files to see which bits were moved where. While this new feature may not represent the most ideal solution to the "plain text attack" problems, it should suffice for this experimental version of BCRP, and should help illustrate the viability of the bit-shuffling methodology developed for the BCRP program.

README.FAQ

FAQ for Cryptography Of A Sort (BCRP - using sorted bit-moves)

Q: Is BCRP an actual product?

A: BCRP is an encryption engine supplied in source-code format, which calls some commonly available (and replaceable) functions included with commercial computer-language libraries, which in turn perform some of the rudimentary tasks required by the program. Public Key features are not currently supported in BCRP, therefore, messaging applications are not as well supported as is local file encryption.

Q: What are the main differences between BCRP and other non-messaging-oriented crypto products?

A: 1. BCRP repositions bits based on multiple encoding passes using one or more Pseudo-Random Number Generators (PRNG's). Since BCRP is provided only in source code format, and since the source code calls its own PRNG function, BCRP is actually independent of any compiler's internal PRNG.

NOTE: PRNG limitations, as described in the popular literature, do not necessarily apply when repositioning bits in multiple passes, as opposed to modifying bits as is normally done in other software.

Think of "brute force encryption" (more on this below).

2. BCRP does not use a "key" as such, and thus does not "encrypt" the bits in a text bitstream. Instead, it uses an input value (text or numeric) as an entry point into a common PRN sequence. Since the entry point is a secret, and since bits are moved using random block sizes, from their original bytes into unrelated destination bytes, cryptanalytic attempts must necessarily begin with brute-force guessing as to the entry points in the PRN sequences, in order to associate the correct bits with their original bytes of text. Multiple encoding passes raise the number of guesses exponentially.

3. BCRP source code is extremely small, the primary intent for which was to provide a sample encoding engine for local/personal computer files.

Due to its small size and simplicity, the source code can be easily modified by casual users, who may add in their own custom routines.

NOTE: It cannot be overemphasized, that crypto programs which have a widely-respected reputation must also be held suspect when A) The very nature of those programs is to deceive, -and- B) The source code is either not available, or is so complex as to discourage ordinary people from working with it.

Q: But if BCRP uses a common, ordinary PRNG, how can it possibly be secure?

A: I can think of two arguments against using PRNG's: 1. Encoded text is easy to decode by brute force on most computers, -and- 2. Encoded text can be seen as having regular patterns when "viewed" from the vantage point of programs employing higher-dimensional mathematics.

Addressing the former, a single-pass encryption of a text file using the typical PRNG might be breakable in as little as .000001 second on one of the larger, faster computers available, however, the same approach might require as many as 10^24 years if the number of encoding passes reaches ten or more. To simplify: try to guess the number I'm thinking between zero and 32,000. You can make 16 billion guesses per second, so it will take only .000001 second (on average) to get the correct answer. If you had to guess ten numbers correctly (and sequentially), it would require roughly (16,000^10) / 16,000,000,000 seconds, approximately 10^24 years.

Addressing the latter, the ability to "view" the text as a lattice in a higher dimension is likewise diminished by the discontinuities inherent in multi-pass encoding, when bit-group sizes are determined dynamically by PRN's following the secret entry points into the PRNG sequences.

Q: Since BCRP only moves bits and doesn't change any of them, wouldn't that make cryptanalysis much easier, since the number of 0-bits and 1-bits in the encrypted file would be identical to the numbers in the source file?

A: While the BCRP encryption processes don't actually change any bits, the bit-padding and de-padding options in versions 3.x and above will allow you to change 8th bits to 1's in "7-bit" ASCII text, after which you do any encryption steps followed (eventually) by decryption and de-padding.

Q: What about the possibility that two or more encryption passes could be decrypted in a single pass, as in the scenario where a third key K3 is functionally equivalent to two separate encrypting keys K1 and K2?

A: Since BCRP encoding is controlled through entry points into a PRNG's number sequences (adjacent encryptions may also use different PRNG's and/or bit-move logic), searching for a "key" or algorithm which can unpack two or more layers of coding will prove futile when all entry points into the PRNG's are different, and different PRNG's are used.

A couple of points to consider: One, the output of the PRNG (or any number series) does not describe the bit move-to locations; those are determined by sorting the PRN's then moving the bits according to the sequence of the original array positions of the PRN's prior to sorting. Since some of the PRN's are duplicates, the original array positions relative to each other will be determined by chance, i.e., the vagaries of the sort process, etc.

Two, since the bits are moved rather than modified, and since groups of bits vary in size, an attempt to find particular bits that belong to specific bytes after multi-move shuffling, using any compound key or algorithm in a single decoding pass, will certainly prove futile.

Q: Since the personal computer implementation of BCRP uses 15-bit integers to initialize (set entry points into) the PRNG's, would ten encryption passes be somehow equivalent to the use of a 150-bit key in conventional programs?

A: If the conventional program used a 150-bit key in a manner similar to BCRP, it would still have to: 1) move bits, not change them. 2) use an indirect method for specifying move locations. 3) model the processes used in BCRP quite closely, since there's no straightforward mathematical approach that can duplicate the conditions described in the previous question and answer.

Q: What's the difference between the techniques used by BCRP and the use of a One-Time Pad (OTP)?

A: The theory behind the OTP assumes that (unlike the use of a Public/Private key) subsequent encryptions using the same OTP key would reveal the nature of the OTP, i.e., any newly-encoded files and messages would share certain common identifiable characteristics which could be exploited to facilitate the decryption of all files using that pad.

BCRP, on the other hand, doesn't alter any of a file's bits, and therefore does not "add" its PRNG entry points' characteristics to a file other than shuffling bits in accordance with the original physical positions of PRN's which have been sorted by size.

Q: Is it possible for anyone to alter the contents of files encrypted by BCRP so that a person performing the eventual decryption would not realize that the file(s) were indeed altered?

A: Less likely than incidental or brute-force decryption. Each bit is moved once in each encryption pass, and if any bits were moved or changed, that many bytes (or nearly as many, since bits are not moved in byte-divisible groups, so most will end up in unrelated bytes after encryption) would be affected, and the resulting bytes would not likely pass even the simplest checksum test.

Q: Is BCRP a "weak" product (cryptographically speaking), either because of limitations in its own internal algorithms, or in the commercial library functions it calls?

A: BCRP can be used in ways that produce weak encryption, which is really an advantage in encouraging beginners to get started, given its simple user interface. Whether it can produce "strong" encryption or not is a matter of opinion, where said opinion is not so much a function of the product's alleged weaknesses, as it is the fact that cryptography grew up from a long history of hand-ciphering and the mathematics attending that growth, and the obvious resistance to new paradigms in this field.

While mathematical proof of encryption strength is highly desirable in most applications (some would argue essential in certain applications), I see things this way: Computer software of any kind, which cannot be analyzed by common persons (average programmers), whose innards cannot be exposed to the masses for whatever reason, should not be used where it could effect control over the lives of those people. Looking at it a different way, it's wise for any individual or group to evaluate the software that's available, and make their own judgements independently of "expert opinion" in the field.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.