Channels ▼
RSS

$3,000 Prize Offered in Cryptography Contest


$3,000 Prize Offered in Cryptography Contest

Using a BASIC language encryption utility, BCRP.EXE, I have encrypted a test file, TEST5.DAT, and have issued this challenge: $3,000 (U.S.) will be awarded to the first party to submit proof of decrypting TEST5.DAT. 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.

Creating BCRP

The encryption routine presented here was originally developed in early February, 1996. From September 1996 through March 1997, concurrent with my tour on the "Cypherpunks" forum, I modified the program slightly and produced the README.FAQ file (see below).

I've been sitting on this project for about three years, waiting to see what kinds of changes would occur in the security and encryption fields, and how "trusted" programs such as PGP would fare when their use became much more widespread. Differential Fault Analysis showed up some of the potential weaknesses in conventional programs such as PGP, and recently it was "discovered" that PGP had a flaw that allowed attackers to place their own public key into someone else's key file, allowing an attacker to decrypt messages that they should not be able to read at all!

My feeling is that modern crypto systems are fundamentally flawed in that they typically mask a relatively small key against a (relatively) large file, in such a manner that the coding is weakened in ways most persons will never be aware of. Some of those weaknesses surfaced in the papers on Differential Fault Analysis.

My solution is to move the bits within a file into more-or-less random positions, specified indirectly by a Pseudo-Random Number stream, then by repeating that process any number of times, increase the randomness of the bit distribution. My degree-of-randomness arguments are:

  1. Each encryption pass, with its own password number, moves the bits within variable-size groups, where each group size is specified by one of the numbers in the PRN stream. Each pass thus adds a layer of randomness to the eventual encryption.

  2. Since bit-group sizes are different within each layer, and because group sizes also change from layer to layer, there is no algorithm that can decrypt multiple layers in a single pass, nor is there an algorithm which can determine partial success, knowing that it has correctly decrypted any individual layer. One of the reasons that algorithms cannot be constructed as mentioned is because the group sizes and move-to positions are not specified by the values of the numbers themselves, but indirectly using the results of a separate sorting process.

  3. To defeat any shortcut comparison methods using plain-text attacks, where an opponent has your secret encrypted text, and also manages to have other files of yours encrypted with the same passwords and with their matching plain text files, the DOS filename is combined with the password number to create a new number that is unique for each file. This new number begins the encryption process in place of the original password so that even though several files may use the same passwords, their bits will not be moved the same way with the same bit-group sizes at the same offset positions in the files. Note that while this DOS filename method may not be the permanent solution for plain-text attacks, it should help to illustrate the viability of the bit-moving methodology used in the BCRP program.

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 those secrets are 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 $3000 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 TEST5.DAT file was encrypted with the BCRP.EXE program with two steps of processing, using the DOS command line as follows:

Step 1: BCRP TEST5.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 TEST5.DAT /E n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12

(n1, n2, n3, etc. = passwords, all numeric)

To decrypt the TEST5.DAT file, reverse the process as follows:

Step 1: BCRP TEST5.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 TEST5.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 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:

  1. 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.

  2. 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.

  3. 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:

    1. 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".

    2. 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 TEST5.DAT file:

    1. The sole purpose of the $3,000 (U.S.) award is to prove whether or not the TEST5.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 TEST5.DAT file. Any claim of success using the exhaustive search method cannot be validated, since the number of attempts required to decrypt TEST5.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 README.FAQ 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.

    2. All claims must be submitted by e-mail to [email protected] or by postal mail to Dale Thorn, 209 4th Street #A, Seal Beach, CA, 90740, and must be postmarked on or before January 31, 2001.

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

    4. Any person who requests the ability to decrypt the TEST5.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 Feb. 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 and that no tricks, traps, or other concealed artifacts were utilized to encrypt the TEST5.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.

    5. Only one award of $3,000 will be paid to the first successful entry, unless there are ties on the earliest submittal, in which case the award will be split evenly between the successful claimants.

    6. Any person who successfully decrypts the TEST5.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 unencrypted 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 (PRNGs). 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 PRNGs: 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 reach 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 PRNs 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 ones 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 PRNGs and/or bit-move logic), searching for a "key" or algorithm that can unpack two or more layers of coding will prove futile when all entry points into the PRNGs are different, and different PRNGs 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 PRNs prior to sorting. Since some of the PRNs 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 PRNGs, 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 PRNs 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.