|
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.
December 01, 2000
URL:http://www.drdobbs.com/3000-prize-offered-in-cryptography-conte/184404414
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.
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:
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.
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.
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.
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:
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.
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.
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.