1) Why is this bozo cluttering up my computer with a 12K file?
2) What are the design goals of Quadibloc?
3) Where can I get source code?
4) What are the known weaknesses of Quadibloc?
5) How could it have been made stronger?
6) Where does Quadibloc get its security from?
7) How does Quadibloc compare to DES?
8) How does Quadibloc compare to Skipjack?
9) How does Quadibloc compare to Blowfish?
10) What is the likely impact of Quadibloc?
Obviously a shameless attempt to obtain 15 minutes of fame by getting mentioned in the third edition of Schneier.
There are three goals, in the following order:
- Ease of implementation,
- Security, and
- Efficiency in software and hardware.
The primary goal, ease of implementation, was addressed by keeping the size and number of S-boxes in the cipher to a minimum. Ease of implementation and efficiency were also promoted by keeping the few bit transposes in the cipher simple. Because of the order of the goals, security was obtained by performing part of the F-function twice, rather than relying on fancier S-boxes, and a full bit-transpose was included ONCE in the cipher.
I haven't written any yet. Maybe in a couple of years. At least, in addition to distributing the source, I'll NEED to implement it at least once in order to generate test vectors. Which everyone else will probably want before they try their hands at it.
QUADIBLOC-640 can have its effective key size shortened by from 32 to 64 bits through a meet-in-the-middle attack.
Since Quadibloc uses one S-box all the way across in the F-function, if Quadibloc had weak keys (which, fortunately, it doesn't) it would have a rotational symmetry for all rotations of a multiple of 8 bits applied to the two halves of the block together. The permutation after round 8 also limits the damage this would do.
It probably has much worse ones than that, but I don't have the prestige to get Eli Biham et al to do my work for me... .
Other possible weaknesses:
Does doing an XOR after the substitution and P-permutation in the F-function leak key bits?
Should an odd value, instead of 8 bits, be used for the circular shift done along with the swap of halves?
The F-function is more complicated than that of DES in some ways, but unlike that of DES, it isn't a one-way hash; it's invertible.
The P-permutation, and the "wall" permutation used after round 8, are both regular.
The use of a single S-box all the way across in the f-function also means that if characteristics are found for applying differential cryptanalysis, it is easier to use them in successive rounds. However, the fact that the S-box has 256 entries, the fact that the f-function is doubled, and the use of S-box 2 on the left half, all make a differential attack unlikely.
The use of a permutation after round 8 is not as total an obstacle to analysis as I had originally thought. It is no hindrance whatever to the boomerang attack, discussed in the section on differential cryptanalysis. However, in addition to a permutation, I also put the right half of the block through S2 both before and after (the left half goes through S2 anyways). Thus, it does not appear at this time that the boomerang attack requires immediate alterations to the QUADIBLOC design.
I can think of two obvious improvements that I avoided for the sake of ease of implementation.
- Replace the swap plus circular shift with a straight swap, but in ALL 16 rounds, after the XOR, and before the second use of S-box 2, do a right circular shift of 12 bits on the left half of the block.
- Replace S-boxes 1 and 2 by two sets of 8 S-boxes.
DES could be made TOTALLY insecure by stripping just TWO elements from it:
- remove the expansion permutation, changing all the S-boxes to have 4 inputs as well as 4 outputs;
- replace the permutation P with the identity permutation.
Then, DES would become a set of 8 ciphers applied to 8 blocks of 8 bits.
Quadibloc relies on the fact that it uses a simple S-box followed by a regular P permutation, and repeats that process twice. The first application substitutes for the expansion permutation, as well as providing some security of its own.
In addition, after round 8, a non-keyed scramble that makes every bit of the block depend on every other bit is applied, in hopes of frustrating analysis. S-box 2 gets extra use here, but the bit transpose differs from the rest of the cipher.
The key is expanded slightly, from 160 bits to 176 bits, using a 4 of 8 code. The 4 of 8 code is not intended to have any security properties, since it would not contribute to the security of the cipher if it were more random. What it DOES do is eliminate weak keys, like all zeroes or all ones.
Also, by XORing key material before AND after the use of S box 1, complementation properties are eliminated.
DES has a 56 bit key, 48 bits of which are used in each round.
Quadibloc has a key of 160 bits. This is expanded to 176 bits; then, 128 bits are used in each round to generate an effective round subkey which is 96 bits in length.
DES uses engineered S-boxes with auxiliary inputs from adjacent nibbles for heightened nonlinearity, and an irregular bit transpose P. The S-boxes are based on multiple permutations of (0..15). The key material is applied by an XOR prior to using the S-boxes.
Quadibloc uses a random S-box containing a single permutation of (0..255) and a regular bit transpose. But this is applied twice, and key material is XORed three times, at the start, in the middle, and at the end.
DES simply XORs the f-function output with the left half.
Quadibloc uses a second S-box before and after the XOR with the f-function output. Thus, plaintext actually goes through an S-box, which seems intuitively more satisfying.
Originally, I wrote the following:
How should I know? After all, it is secret, and I have had no access to the secret.
However, some comparisons can be made on the basis of publicly available information.
Quadibloc was deliberately designed to have two desirable properties claimed for Skipjack: no 'weak keys', and freedom from complementation properties.
Quadibloc has only 16 rounds, not 32 as for Skipjack.
Quadibloc has a 160-bit key, which is longer than an 80-bit key.
Quadibloc does not have a 48-bit internal structure.
Quadibloc was designed to be easy to implement, and has S-boxes of minimal size.
Quadibloc was designed in one weekend by one person with neither any particularly relevant academic credentials nor relevant cryptanalytic experience (hey, I do have an M.Sc. in Nuclear Physics!). Skipjack was designed by the top cryptographers and cryptanalysts in the U.S., entrusted with guarding the nation's security.
You and I don't get to make use of Skipjack without key escrow, Quadibloc doesn't have this problem.
(Note that, since this was written, Fortezza PCMCIA cards without key escrow were made available to the public in the U. S., which was an interesting, and perhaps even amusing, development in the ongoing Clipper Chip saga.)
Quadibloc is available for open review. However, it is probably so insignificant that it will never recieve any such review.
At present, I no longer have the excuse I began that section with, as Skipjack has now been declassified. (I write these words as part of the update of these pages to include its description!)
Skipjack has a regular key schedule, which would seem to open up the possibility of related-key attacks; Quadibloc has an irregular one, based on that of DES.
Quadibloc's f-function has two stages to it, which was an apparent innovation at the time. However, Skipjack's G permutation is actually a four-round miniature block cipher with a 16-bit block.
Skipjack is both easier to implement than Quadibloc, and more efficient.
Quadibloc-40, Quadibloc-64, and Quadibloc-80 all have a relatively simple method of expanding the key size to 160 bits; they do not explode the work factor in the way Blowfish does to handicap attempts at brute-force searching. This was done deliberately, both for ease of implementation, and in hopes that Quadibloc-40 might be approved for export, thus giving U.S. software authors a royalty-free alternative.
The natural key size of Quadibloc is only 160 bits, while Blowfish makes full use of a key up to 384 bits in length.
On the other hand, the added complexity of the F-function may be to the credit of Quadibloc. On balance, though, it may be fair to say that the advantages of Blowfish over Quadibloc in security are of a sort likely to have real- world value, while the advantages of Quadibloc are of a more theoretical nature.
- revealing Quadibloc to unevolved uninitiates may lead to burdening of my karma
Not worried. Saddam Hussein has already heard of IDEA, Triple-DES, Blowfish...if the NSA thinks I have endangered U.S. national security, then they've done so, by choosing to live in a fool's paradise.
- NSA releases Skipjack patent in order to prevent use of Quadibloc
Probability slightly lower than that of one of the primes in your RSA modulus actually being a Carmichael number.
- Complications of Quadibloc found illusory; new cryptanalytic method discovered that is an extension of differential/linear cryptanalysis
I can dream, can't I? That would be a noble way to have failed.
The intent of boring the world with yet another block cipher should, however, be stated.
Due to restrictions on source code export, (which may not apply to us lucky Canadians) I have chosen to lead the way in showing that a secure algorithm can be designed to be so simple to implement that coding it is trivial, and does not depend on giant S-boxes or difficult mathematics which requires access to a reference source code implementation.
Also, Quadibloc illustrates techniques that could be applied to other ciphers. Doubling the F-function is possible in Blowfish quite simply (you will need more pi); and it could even be done in DES, with more violence to the key schedule. (In fact, it is probably one of the more secure ways to create a 112-bit key DES variant.)
Start of Section
Skip to Next Section
Table of Contents