Article 13268 of alt.sources:
Path: nntpd.lkg.dec.com!pa.dec.com!decwrl!amd!netcomsv!uu4news.netcom.com!netcomsv!uu3news.netcom.com!ix.netcom.com!howland.reston.ans.net!vixen.cso.uiuc.edu!newsfeed.internetmci.com!in2.uu.net!news.cais.net!nntp.uio.no!solace!news.ifm.liu.se!usenet
From: nisse@lysator.liu.se (Niels Möller)
Newsgroups: alt.sources,sci.crypt
Subject: ISO_MAA - The ISO-8731-2 Message Authentication Algorithm
Followup-To: sci.crypt
Date: 20 Mar 1996 00:30:04 +0100
Organization: Lysator Computer Society, Link|ping University, Sweden
Lines: 627
Sender: nisse@tintin.lysator.liu.se
Message-ID: <nnlokw1x1f.fsf@tintin.lysator.liu.se>
NNTP-Posting-Host: tintin.lysator.liu.se
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
X-Newsreader: Gnus v5.1
Xref: nntpd.lkg.dec.com alt.sources:13268 sci.crypt:50668

Submitted-by: nisse@lysator.liu.se
Archive-name: ISO_MAA

What follows is an implementation of the ISO-8731-2 Message
Authentication Algorithm, written in C. For those of you who don't
know, this is a 32-bit MAC (Message Authentication Code) with a 64-bit
secret key, used in the banking world. I apologize if this rather long
source posting is inappropriate in sci.crypt, but I hope some of you
find it useful.


Portability

I assume that long is 32 bits and long long is 64 bits. If this is
incorrect, you will have to modify the corresponding macros. Except
for this, the code should be fully portable.


Copying policy

I do like the GNU General Public License. However, this is a rather
small piece of code, and it follows the ISO standard document very
closely, so I have decided to release it to the public domain. This
means: Do whatever you like with it.

Nevertheless, I'd like know if you improve it or find any bugs. The
code is tested, but not *thouroughly* tested. If you define MAA_TEST
when compiling ISO_MAA.c, a main() function is compiled in that
performs a few tests (also taken from the ISO document).


CAVE

I won't take any responsibility that this code works. And even *if* it
works, I don't recommend using this algorithm. It hasn't been
completely broken (yet), but it does have a few flaws (see
ftp://ftp.esat.kuleuven.ac.be/pub/COSIC/preneel/twomacs.ps.gz ). If
you are in a position to choose which algorithm to use, don't choose
this one.

I don't know of any patents or export restrictions that applies, but
that doesn't necessarily imply that there are none.


8-bit transmissions

I'm trying to follow the alt.sources standards, using a shar archive
and no extra encoding. However, as the source files include my name,
which contains the 'ö' character (octal 366, o with two dots above
it), this will break if some braindead newsserver on the path strips
this message to 7 bits. You can recognize this damage by two lines saying

* C implementation by Niels Mvller <nisse@lysator.liu.se> 1996
                             ^
You then have to replace the 'v' character with the proper one, if you
want the md5 checksum to match. And don't forget to tell your sysadm
that the software is broken. See http://www.lysator.liu.se/åttabitars
for some arguments for using our 8:th bit.


Documentation

The source is the documentation. A copy of the ISO standard may be
helpful too. Beware that padding of messages is *not* defined in the
standard, and I don't handle it either. That means that messages must
be an even number of blocks. Usage is as follows:

* Initialize a MAA_key struct.
* Call MAA_key to prepare the key for use.
* Initialize a MAA_state struct, including a pointer to the key prepared
above.
* Call MAA_update one or several times to process a message.
* Call MAA_mac, which will return the MAC for the message, and reset
the state for processing a more messages.


Happy Hacking!

/Niels Möller

---- Cut Here and feed the following to sh ----
#!/bin/sh
# This is ISO_MAA, a shell archive (produced by GNU sharutils 4.2)
# To extract the files from this archive, save it to some FILE, remove
# everything before the `!/bin/sh' line above, then type `sh FILE'.
#
# Made on 1996-03-19 23:19 MET by <nisse@lysator.liu.se>.
# Source directory was `/home/lysdisk2/nisse/xjobb/src'.
#
# Existing files will *not* be overwritten unless `-c' is specified.
#
# This shar contains:
# length mode       name
# ------ ---------- ------------------------------------------
#    844 -rw-r--r-- ISO_MAA.h
#   8548 -rw-r--r-- ISO_MAA.c
#
save_IFS="${IFS}"
IFS="${IFS}:"
gettext_dir=FAILED
locale_dir=FAILED
first_param="$1"
for dir in $PATH
do
  if test "$gettext_dir" = FAILED && test -f $dir/gettext \
     && ($dir/gettext --version >/dev/null 2>&1)
  then
    set `$dir/gettext --version 2>&1`
    if test "$3" = GNU
    then
      gettext_dir=$dir
    fi
  fi
  if test "$locale_dir" = FAILED && test -f $dir/shar \
     && ($dir/shar --print-text-domain-dir >/dev/null 2>&1)
  then
    locale_dir=`$dir/shar --print-text-domain-dir`
  fi
done
IFS="$save_IFS"
if test "$locale_dir" = FAILED || test "$gettext_dir" = FAILED
then
  echo=echo
else
  TEXTDOMAINDIR=$locale_dir
  export TEXTDOMAINDIR
  TEXTDOMAIN=sharutils
  export TEXTDOMAIN
  echo="$gettext_dir/gettext -s"
fi
touch -am 1231235999 $$.touch >/dev/null 2>&1
if test ! -f 1231235999 && test -f $$.touch; then
  shar_touch=touch
else
  shar_touch=:
  echo
  $echo 'WARNING: not restoring timestamps.  Consider getting and'
  $echo "installing GNU \`touch', distributed in GNU File Utilities..."
  echo
fi
rm -f 1231235999 $$.touch
#
if mkdir _sh28986; then
  $echo 'x -' 'creating lock directory'
else
  $echo 'failed to create lock directory'
  exit 1
fi
# ============= ISO_MAA.h ==============
if test -f 'ISO_MAA.h' && test "$first_param" != -c; then
  $echo 'x -' SKIPPING 'ISO_MAA.h' '(file already exists)'
else
  $echo 'x -' extracting 'ISO_MAA.h' '(text)'
  sed 's/^X//' << 'SHAR_EOF' > 'ISO_MAA.h' &&
/* MAA - Message Authentication Algorithm - ISO 8731-2
X *
X * C implementation by Niels Möller <nisse@lysator.liu.se> 1996
X */
X
#ifndef ISO_MAA_H_INCLUDED
#define ISO_MAA_H_INCLUDED
X
/* 32 bit integer */
#define MAA_WORD unsigned int
X
struct MAA_key
{
X  MAA_WORD J, K;
X  MAA_WORD X0, Y0, V0;
X  MAA_WORD W, S, T;
};
X
struct MAA_state
{
X  struct MAA_key *key;
X  MAA_WORD X, Y, V;
X  unsigned buffer_count;
X  unsigned char buffer[4];
X  unsigned block_count;
};
X
void  /* Preprocess key */
MAA_key(struct MAA_key *key, MAA_WORD j, MAA_WORD k);
X
void  /* Initialize */
MAA_reset(struct MAA_state *state);
X
void  /* Hash more data */
MAA_update(struct MAA_state *state,
X	   unsigned char *message,
X	   unsigned length);
X
MAA_WORD /* Get Message Authentication Code for message, and reset */
MAA_mac(struct MAA_state *state);
X
#endif ISO_MAA_H_INCLUDED
SHAR_EOF
  $shar_touch -am 0306151396 'ISO_MAA.h' &&
  chmod 0644 'ISO_MAA.h' ||
  $echo 'restore of' 'ISO_MAA.h' 'failed'
  if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
  && ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
    md5sum -c << SHAR_EOF >/dev/null 2>&1 \
    || $echo 'ISO_MAA.h:' 'MD5 check failed'
3e19b960243b018b4ff74706cb4a70a4  ISO_MAA.h
SHAR_EOF
  else
    shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'ISO_MAA.h'`"
    test 844 -eq "$shar_count" ||
    $echo 'ISO_MAA.h:' 'original size' '844,' 'current size' "$shar_count!"
  fi
fi
# ============= ISO_MAA.c ==============
if test -f 'ISO_MAA.c' && test "$first_param" != -c; then
  $echo 'x -' SKIPPING 'ISO_MAA.c' '(file already exists)'
else
  $echo 'x -' extracting 'ISO_MAA.c' '(text)'
  sed 's/^X//' << 'SHAR_EOF' > 'ISO_MAA.c' &&
/* MAA - Message Authentication Algorithm - ISO 8731-2
X *
X * C implementation by Niels Möller <nisse@lysator.liu.se> 1996
X */
X
#include <ISO_MAA.h>
#include <stdio.h>
X
/* 64 bit integer */
#define DWORD unsigned long long
X
/* Constants */
#define MAA_A 0x02040801
#define MAA_B 0x00804021
#define MAA_C 0xbfef7fdf
#define MAA_D 0x7dfefbff
X
/* Primitive operations */
static inline MAA_WORD
CYC(MAA_WORD x)   /* Cyclic shift one bit left */
{ 
X  return (x << 1) | (x>>31);
}
X
#define AND(x,y) ((x) & (y))
#define OR(x,y) ((x) | (y))
#define XOR(x,y) ((x) ^ (y))
X
/* Addition mod 2^32 */
#define ADD(x,y) ((x) + (y))
X
static inline MAA_WORD
CAR(MAA_WORD x, MAA_WORD y)  /* Carry when adding x and y */
{
X  return x > (0xffffffff - y);
}
X
static inline DWORD
MUL64(MAA_WORD x, MAA_WORD y)  /* 32*32 -> 64 bit addition */
{
X  DWORD z = (DWORD) x * y;
X  return z;
}
X
static inline MAA_WORD
MUL1(MAA_WORD x, MAA_WORD y)   /* Result = x * y (mod 2^32-1) */
{
X  DWORD z;
X  MAA_WORD l, u;
X
X  z = MUL64(x,y);
X  u = z >> 32; l = z & 0xffffffff;
X  return ADD(ADD(u,l), CAR(u,l));
}
X
static inline MAA_WORD
MUL2(MAA_WORD x, MAA_WORD y)  /* Result = x * y (mod 2^32 - 2) */
{
X  DWORD z;
X  MAA_WORD l, u, f;
X  
X  z = MUL64(x,y);
X  u = z >> 32; l = z & 0xffffffff;
X
X  f = ADD(ADD(u,u), 2*CAR(u,u));
X  return ADD(ADD(f,l), 2*CAR(f,l));
}
X
static inline MAA_WORD
MUL2A(MAA_WORD x, MAA_WORD y) /* Alternative to MUL2, that works if the
X		               * most significant bit of at least one
X		               * of the arguments is 0. */
{
X  DWORD z;
X  MAA_WORD l, u, d;
X
X  z = MUL64(x,y);
X  u = z >> 32; l = z & 0xffffffff;
X  d = ADD(u,u);
X  return ADD(ADD(d,l), 2*CAR(d,l));
}
X
static inline unsigned char
OCTET(unsigned i, MAA_WORD x) /* Extract the i:th most significant byte */
{
X  return (x >> (24 - 8*i)) & 0xff;
}
X
static inline MAA_WORD
ASSEMBLE_OCTETS(unsigned char c[4]) /* Put 4 octets together to a word */
{
X  unsigned i;
X  MAA_WORD x;
X  
X  for (i = 0, x = 0; i<4; i++)
X    x = (x<<8) + c[i];
X  return x;
}
X
static unsigned char
BYTPAT(MAA_WORD x, MAA_WORD y,
X       MAA_WORD *x1, MAA_WORD *y1)   /* Avoid strings of ones and zeros */
{
X  unsigned i;
X  unsigned char b[8];
X  unsigned char p;
X
X  /* Convert to octets */
X  for (i=0; i<4; i++)
X    {
X      b[i]   = OCTET(i, x);
X      b[4+i] = OCTET(i, y);
X    }
X
X  for (p = 0, i = 0; i<8; i++)
X    {
X      p *= 2;
X      switch (b[i])
X	{
X	case 0:
X	  p++;
X	  b[i] = p;
X	  break;
X	case 0xff:
X	  p++;
X	  b[i] = 0xff - p;
X	  break;
X	default:
X	  ;
X	}
X    }
X
X  *x1 = ASSEMBLE_OCTETS(b);
X  *y1 = ASSEMBLE_OCTETS(b+4);
X  return p;
}
X
X
/* Shorthands used below */
#define MUL3(z, x, y) do { \
X  z[0] = MUL1(x[0],y[0]); z[1] = MUL2(x[1], y[1]); \
} while (0)
X
#define XOR2(h, j) ((h) = XOR((j)[0], (j)[1]))
X
static void
PRELUDE(struct MAA_key *key)
{
X  MAA_WORD j1, k1;
X  MAA_WORD j2[2], j4[2], j6[2], j8[2];
X  MAA_WORD h4, h6, h8, h1, h5, h7, h9;
X  MAA_WORD k2[2], k4[2], k5[2], k7[2], k9[2];
X  unsigned char p;
X  MAA_WORD q;
X  
X  p = BYTPAT(key->J, key->K, &j1, &k1);
X  q = (1 + p) * (1 + p);
X
X  j2[0] = MUL1(j1, j1); j2[1] = MUL2(j1, j1);
X  MUL3(j4, j2, j2);
X  MUL3(j6, j2, j4);
X  MUL3(j8, j2, j6);
X
X  XOR2(h4, j4);
X  XOR2(h6, j6);
X  XOR2(h8, j8);
X
X  k2[0] = MUL1(k1, k1);    k2[1] = MUL2(k1, k1);
X  MUL3(k4, k2, k2);
X  k5[0] = MUL1(k1, k4[0]); k5[1] = MUL2(k1, k4[1]);
X  MUL3(k7, k2, k5);
X  MUL3(k9, k2, k7);
X
X  XOR2(h1, k5);
X  h5 = MUL2(h1, q);
X  XOR2(h7, k7);
X  XOR2(h9, k9);
X
X  BYTPAT(h4, h5, &(key->X0), &(key->Y0));
X  BYTPAT(h6, h7, &(key->V0), &(key->W));
X  BYTPAT(h8, h9, &(key->S), &(key->T));
}
X
void
MAA_key(struct MAA_key *key, MAA_WORD j, MAA_WORD k)
{
X  key->J = j; key->K = k;
X  PRELUDE(key);
}
X
inline void
MAA_reset(struct MAA_state *state)
{
X  state->X = state->key->X0;
X  state->Y = state->key->Y0;
X  state->V = state->key->V0;
X  state->block_count = state->buffer_count = 0;
}
X
static inline void
MAA_loop(struct MAA_state *state, MAA_WORD m)
{
X  MAA_WORD e, f, g;
X  
X  state->V = CYC(state->V);
X  e = XOR(state->V, state->key->W);
X  state->X = XOR(state->X, m);  state->Y = XOR(state->Y, m);
X  f = AND(MAA_C, OR(MAA_A, ADD(e, state->Y)));
X  g = AND(MAA_D, OR(MAA_B, ADD(e, state->X)));
X
X  state->X = MUL1(state->X, f); state->Y = MUL2A(state->Y, g);
}
X
static MAA_WORD
MAA_coda(struct MAA_state *state)
{
X  MAA_loop(state, state->key->S);
X  MAA_loop(state, state->key->T);
X  return XOR(state->X, state->Y);
}
X
static inline void
MAA_process_block(struct MAA_state *state, MAA_WORD m)
{
X  if (state->block_count == 256)
X    {
X      MAA_WORD z = MAA_coda(state);
X      MAA_reset(state);
X      MAA_loop(state, z);
X      state->block_count = 0;
X    }
X  MAA_loop(state, m);
X  state->block_count++;
}
X
void
MAA_update(struct MAA_state *state,
X	   unsigned char *message,
X	   unsigned length)
{
X  while ((length > 0) && (state->buffer_count < 4))
X    {
X      state->buffer[state->buffer_count++] = *message++;
X      length--;
X    }
X  if (state->buffer_count == 4)
X    {
X      MAA_process_block(state, ASSEMBLE_OCTETS(state->buffer));
X      for ( ; length >= 4; length -= 4, message += 4)
X	MAA_process_block(state, ASSEMBLE_OCTETS(message));
X      for (state->buffer_count = 0; length; length--)
X	state->buffer[state->buffer_count++] = *message++;
X    }
}
X
MAA_WORD
MAA_mac(struct MAA_state *state)
{
X  MAA_WORD z;
X  if (state->buffer_count)
X    {
X      fprintf(stderr, "MAA: Not an even number of blocks,\n"
X	      "and no padding method defined.\n");
X      abort();
X    }
X  z = MAA_coda(state);
X  MAA_reset(state);
X  return z;
}
X
#ifdef MAA_TEST
X
void
test_prelude(struct MAA_key *key, MAA_WORD x0, MAA_WORD y0,
X	     MAA_WORD v0, MAA_WORD w, MAA_WORD s, MAA_WORD t)
{
X  PRELUDE(key);
X  if ((x0 != key->X0)
X      || (y0 != key->Y0)
X      || (v0 != key->V0)
X      || (w != key->W)
X      || (s != key->S)
X      || (t != key->T))
X    {
X      printf("Prelude failed!\n"
X	     "Expected: [%8x, %8x, %8x, %8x, %8x, %8x]\n"
X	     "Got:      [%8x, %8x, %8x, %8x, %8x, %8x]\n",
X	     x0, y0, v0, w, s, t,
X	     key->X0, key->Y0, key->V0, key->W, key->S, key->S);
X    }
}
X
void
test_round(struct MAA_state *state, MAA_WORD block,
X	   MAA_WORD x, MAA_WORD y)
{
X  MAA_process_block(state, block);
X  if ((x != state->X) || (y != state->Y))
X    {
X      printf("Round failed!\n"
X	     "Expected: [%8x, %8x]\n"
X	     "Got:      [%8x, %8x]\n",
X	     x, y, state->X, state->Y);
X    }
}
X
MAA_WORD test_output[20][2] =
{
X  {0x303ff4aa, 0x1277a6d4},
X  {0x55dd063f, 0x4c49aae0},
X  {0x51af3c1d, 0x5bc02502},
X  {0xa44aaac0, 0x63c70dba},
X  {0x4d53901a, 0x2e80ac30},
X  {0x5f38eef1, 0x2a6091ae},
X  {0xf0239dd5, 0x3dd81ac6},
X  {0xeb35b97f, 0x9372cdc6},
X  {0x4da124a1, 0xc6b1317e},
X  {0x7f839576, 0x74b39176},
X  {0x11a9d254, 0xd78634bc},
X  {0xd8804ca5, 0xfdc1a8ba},
X  {0x3f6f7248, 0x11ac46b8},
X  {0xacbc13dd, 0x33d5a466},
X  {0x4ce933e1, 0xc21a1846},
X  {0xc1ed90dd, 0xcd959b46},
X  {0x3cd54deb, 0x613f8e2a},
X  {0xbba57835, 0x07c72eaa},
X  {0xd7843fdc, 0x6ad6e8a4},
X  {0x5eba06c2, 0x91896cfa}
};
X
int main(int argc, char ** argv)
{
X  struct MAA_key key;
X  struct MAA_state state = { key: &key };
X  MAA_WORD mac;
X  unsigned i;
X  
X  key.J = 0x00ff00ff; key.K = 0;
X  test_prelude(&key,
X	       0x4a645a01, 0x50dec930,
X	       0x5cca3239, 0xfeccaa6e,
X	       0x51ede9c7, 0x24b66fb5);
X  MAA_reset(&state);
X  test_round(&state, 0x55555555, 0x48b204d6, 0x5834a585);
X  test_round(&state, 0xaaaaaaaa, 0x4f998e01, 0xbe9f0917);
X  
X  mac = MAA_mac(&state);
X  printf("MAC: %8x\n", mac);
X  if (mac != 0xf14d6e28)
X    printf("Failed!\n");
X
X  test_round(&state, 0xaaaaaaaa, 0x6aebacf8, 0x9db15cf6);
X  test_round(&state, 0x55555555, 0x270eedaf, 0xb8142629);
X
X  mac = MAA_mac(&state);
X  printf("MAC: %8x\n", mac);
X  if (mac != 0xa93bd410)
X    printf("Failed!\n");
X
X  key.J = 0x55555555; key.K = 0x5a35d667;
X  test_prelude(&key, 0x34acf886, 0x7397c9ae,
X	       0x7201f4dc, 0x2829040b,
X	       0x9e2e7b36, 0x13647149);
X  MAA_reset(&state);
X  
X  test_round(&state, 0, 0x2fd76ffb, 0x550d91ce);
X  test_round(&state, 0xffffffff, 0xa70fc148, 0x1d10d8d3);
X  
X  mac = MAA_mac(&state);
X  printf("MAC: %8x\n", mac);
X  if (mac != 0xb99a62de)
X    printf("Failed!\n");
X
X  test_round(&state, 0xffffffff, 0x8dc8bbde, 0xfe4e5bdd);
X  test_round(&state, 0,          0xcbc865ba, 0x0297af6f);
X
X  mac = MAA_mac(&state);
X  printf("MAC: %8x\n", mac);
X  if (mac != 0xa018c83b)
X    printf("Failed!\n");
X
X  MAA_key(&key, 0x80018001, 0x80018000); MAA_reset(&state);
X  for (i=0; i < 20; i++)
X    test_round(&state, 0, test_output[i][0], test_output[i][1]);
X
X  mac = MAA_mac(&state);
X  printf("MAC: %8x\n", mac);
X  if (mac != 0xdb79fbdc)
X    printf("Failed!\n");
}
#endif MAA_TEST
SHAR_EOF
  $shar_touch -am 0306152396 'ISO_MAA.c' &&
  chmod 0644 'ISO_MAA.c' ||
  $echo 'restore of' 'ISO_MAA.c' 'failed'
  if ( md5sum --help 2>&1 | grep 'sage: md5sum \[' ) >/dev/null 2>&1 \
  && ( md5sum --version 2>&1 | grep -v 'textutils 1.12' ) >/dev/null; then
    md5sum -c << SHAR_EOF >/dev/null 2>&1 \
    || $echo 'ISO_MAA.c:' 'MD5 check failed'
aa1b47c7457bd56801a632eba9d26643  ISO_MAA.c
SHAR_EOF
  else
    shar_count="`LC_ALL= LC_CTYPE= LANG= wc -c < 'ISO_MAA.c'`"
    test 8548 -eq "$shar_count" ||
    $echo 'ISO_MAA.c:' 'original size' '8548,' 'current size' "$shar_count!"
  fi
fi
rm -fr _sh28986
exit 0


