Efficient message authentication?

Is the following message authentication algorithm known?
Patented? Known to be broken? Obviously stupid?

It is reasonably efficient, and convenient, to construct
a message authentication code from a block cipher - one
then has less code to write and make errors in.

Unfortunately, if one follows the NIST recommendation,
one then has to encrypt everything twice, once with one
key for security, once with another key for message
authentication. (CMAC, a variant of CCM)

One would like to combine encryption and authentication,
so that one does not have to double encrypt. A number
of simple efficient algorithms have been proposed, most
which failed, and some terrifyingly complicated
efficient algorithms.

OCB is efficient, gives both encryption and
authenticity, and not intolerably complicated, but is
patented in the US. If one's code is not under GNU, one
faces impractically difficult patent negotiations for
code developed or sold within the US.

This post describes another simple efficient algorithm:
Is it known? Patented? Known to be broken? Stupid?

The classic simple algorithm for constructing a MAC
without much extra work, so that the encryption pass
also generates a MAC, is Free MAC, subsequently broken
subsequently reinvented as IGE, infinite garble
extension.

The breaking was followed by a proof
http://groups.google.ca/group/sci.crypt/browse_thread/thread/e1b9339bf9fb5060/62ced37bb9713a39
that anything resembling Free Mac must fail if it uses
linear operations.

But what about irreversible nonlinear operations?

{X} signifies the block encryption of the block X, ECB
mode.

& signifies bitwise and, | signifies bitwise or, +
signifies addition modulo the block size.

The combination of bitwise logical and arithmetic
operations is non linear in the required sense.

Let N be a nonce.

Let P[k] be the kth block of plain text. The last block
must be in a highly redundant format known by the sender
and expected by the recipient - must be reliably
distinguishable from random gibberish.

Let W[k] be the kth block of whitened plain text.

Let T[k] be the kth block of transmitted encrypted text.

W[1] = {N}&{{N}} + P[1]

W[k+1] = {W[k]}&W[k] + P[k+1]

T[1] = {N}|{{N}} + {W[1]}

T[k+1] = {W[k]}|W[k] + {W[k]}

As with free mac the final block P[last] contains a
length count and other fixed data. To check that the
message is authentic, the recipient checks that the
final block of plaintext is in the correct format.

The algorithm is strong if an adversary knowing the
plain text P[k], the ciphertext T[k] and the nonce, but
not knowing the shared secret encryption key, cannot
construct a fake message that decrypts to something
having a correct final block. The adversary never sees
W[k], {W[k]}, {N}, or {{N}} and should not be able to
know them.

The theory underlying this proposed block encryption
mode is that other block encryption modes fail to
provide authentication because in those modes clever
combinations of observed data can look like a legitimate
message. Strong non linearity and irreversibility of
the propagation mode ensures that clever combinations
will look like random garbage.

I therefore dub this block encryption mode MASNEP
(Message authentication by strong nonlinear error
propagation.)

--
----------------------
We have the right to defend ourselves and our property, because
of the kind of animals that we are. True law derives from this
right, not from the arbitrary power of the omnipotent state.

http://www.jim.com/ James A. Donald
.

Relevant Pages

  • Re: Encryption and authentication
    ... have encryption without authentication? ... it seems that encryption couldn't exist without authentication. ... and example is asymmetric key cryptography technology. ... http://www.garlic.com/~lynn/aadsm24.htm#7 Naked Payments IV - let's all go naked ...
    (comp.security.firewalls)
  • Re: New Encryption Idea
    ... performing the 5 reads necessary in the example algorithm results in a delay ... Panama at 400MB/sec, or RC4 at about 90MB/sec, or AES in CTR mode at ... and the speed failings of your design become very clear. ... > Manansala Encryption and Authentication System ...
    (sci.crypt)
  • Meganets "unbreakable" cryptography? Im skeptical.
    ... Meganet makes such grandiose claims that I can't help but ... There's plenty of coverage on secret encryption algorithms ... encryption algorithm that was granted U.S. Patent ... Labor has bought into this "snake oil" and without a doubt ...
    (sci.crypt)
  • Re: Ciphers and their effect on the size of data
    ... We have a security-sensitive client that is wants common authentication between a J2EE environment and a "fat windows client". ... we'll also be facing 4/3 expansion of the payload after encryption. ... This password field will include a digital signature, or the digital signature will be in another XML element in that document. ...
    (sci.crypt)
  • Re: Enigma machine strenght using a computer
    ... cipher with rotors that spin backwards, forwards, stop and start based ... on other rotors, change their values according to the phase of the moon ... encryption less error-prone and they were a cost effective way to get ... case) than not since a wider base uses the same algorithm. ...
    (sci.crypt)