Cryptography-Digest Digest #326, Volume #12 Tue, 1 Aug 00 05:13:01 EDT
Contents:
ripemd-160 implementation (Nikos Mavroyanopoulos)
Re: Small block ciphers (Mack)
Re: Small block ciphers (Mok-Kong Shen)
Re: PRNG cryptoanalysis (Mack)
Re: What is DES3mCBCMACi64pPKCS5? (David A. Wagner)
Re: ripemd-160 implementation (Mark Wooding)
Re: Elliptic Curves encryption (David A. Wagner)
----------------------------------------------------------------------------
From: Nikos Mavroyanopoulos <[EMAIL PROTECTED]>
Subject: ripemd-160 implementation
Date: Tue, 01 Aug 2000 11:35:10 -0700
This is a multi-part message in MIME format.
==============0A892AD219C72790D51B9FE5
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
I attach a ripemd-160 implementation that is based on a sha-1
implementation (also posted here). Thus they share a consistent api.
This is the implementation used in libmhash.
--
Nikos Mavroyanopoulos
==============0A892AD219C72790D51B9FE5
Content-Type: text/plain; charset=iso-8859-1;
name="ripemd.c"
Content-Transfer-Encoding: 8bit
Content-Disposition: inline;
filename="ripemd.c"
/* ripemd.c - Implementation of the RIPE-MD Hash Algorithm
*
* Copyright (C) 2000, Nikos Mavroyanopoulos
* This implementation is placed under the public domain.
*
* Based on the SHA-1 implementation by A.M. Kuchling
*
* Here are the quotes of the original SHA-1 implementation:
*/
/* Copyright (C) 1995, A.M. Kuchling
* Adapted to pike and some cleanup by Niels M�ller.
*
* Based on SHA code originally posted to sci.crypt by Peter Gutmann
* in message <30ajo5$[EMAIL PROTECTED]>.
* Modified to test for endianness on creation of SHA objects by AMK.
* Also, the original specification of SHA was found to have a weakness
* by NSA/NIST. This code implements the fixed version of SHA.
*/
/* The RIPEMD block size and message digest sizes, in bytes */
#define RIPEMD_DATASIZE 64
#define RIPEMD_DATALEN 16
#define RIPEMD_DIGESTSIZE 20
#define RIPEMD_DIGESTLEN 5
/* The structure for storing RIPEMD info */
typedef struct ripemd_ctx {
word32 digest[RIPEMD_DIGESTLEN]; /* Message digest */
word32 count_l, count_h; /* 64-bit block count */
word8 block[RIPEMD_DATASIZE]; /* RIPEMD data buffer */
int index; /* index into buffer */
} RIPEMD_CTX;
void ripemd_init(struct ripemd_ctx *ctx);
void ripemd_update(struct ripemd_ctx *ctx, word8 *buffer, word32 len);
void ripemd_final(struct ripemd_ctx *ctx);
void ripemd_digest(struct ripemd_ctx *ctx, word8 *s);
void ripemd_copy(struct ripemd_ctx *dest, struct ripemd_ctx *src);
/* 32-bit rotate left - kludged with shifts */
#define ROTL(n,X) (((X)<<(n))|((X)>>(32-(n))))
#define f0(x,y,z) (x^y^z)
#define f16(x,y,z) ((x&y)|((~x) & z))
#define f32(x,y,z) ((x|~(y))^z)
#define f48(x,y,z) ((x&z)|(y&(~z)))
#define f64(x,y,z) (x^(y|(~z)))
#define K0 0x00000000
#define K1 0x5A827999
#define K2 0x6ED9EBA1
#define K3 0x8F1BBCDC
#define K4 0xA953FD4E
#define KK0 0x50A28BE6
#define KK1 0x5C4DD124
#define KK2 0x6D703EF3
#define KK3 0x7A6D76E9
#define KK4 0x00000000
#define h0init 0x67452301
#define h1init 0xEFCDAB89
#define h2init 0x98BADCFE
#define h3init 0x10325476
#define h4init 0xC3D2E1F0
void ripemd_copy(struct ripemd_ctx *dest, struct ripemd_ctx *src)
{
int i;
dest->count_l = src->count_l;
dest->count_h = src->count_h;
for (i = 0; i < RIPEMD_DIGESTLEN; i++)
dest->digest[i] = src->digest[i];
for (i = 0; i < src->index; i++)
dest->block[i] = src->block[i];
dest->index = src->index;
}
/* Initialize the RIPEMD values */
void ripemd_init(struct ripemd_ctx *ctx)
{
/* Set the h-vars to their initial values */
ctx->digest[0] = h0init;
ctx->digest[1] = h1init;
ctx->digest[2] = h2init;
ctx->digest[3] = h3init;
ctx->digest[4] = h4init;
/* Initialize bit count */
ctx->count_l = ctx->count_h = 0;
/* Initialize buffer */
ctx->index = 0;
}
#define subRound(a, b, c, d, e, f, k, r, data) \
( a = ROTL( r, a + f(b,c,d) + data + k) + e, c = ROTL(10, c) )
static void ripemd_transform(struct ripemd_ctx *ctx, word32 * data)
{
word32 A, B, C, D, E; /* Local vars */
word32 AA, BB, CC, DD, EE; /* Local vars */
word32 T, t;
/* Set up first buffer and local data buffer */
A = ctx->digest[0];
B = ctx->digest[1];
C = ctx->digest[2];
D = ctx->digest[3];
E = ctx->digest[4];
/* j=0...15 */
subRound(A, B, C, D, E, f0, K0, 11, data[0]);
subRound(E, A, B, C, D, f0, K0, 14, data[1]);
subRound(D, E, A, B, C, f0, K0, 15, data[2]);
subRound(C, D, E, A, B, f0, K0, 12, data[3]);
subRound(B, C, D, E, A, f0, K0, 5, data[4]);
subRound(A, B, C, D, E, f0, K0, 8, data[5]);
subRound(E, A, B, C, D, f0, K0, 7, data[6]);
subRound(D, E, A, B, C, f0, K0, 9, data[7]);
subRound(C, D, E, A, B, f0, K0, 11, data[8]);
subRound(B, C, D, E, A, f0, K0, 13, data[9]);
subRound(A, B, C, D, E, f0, K0, 14, data[10]);
subRound(E, A, B, C, D, f0, K0, 15, data[11]);
subRound(D, E, A, B, C, f0, K0, 6, data[12]);
subRound(C, D, E, A, B, f0, K0, 7, data[13]);
subRound(B, C, D, E, A, f0, K0, 9, data[14]);
subRound(A, B, C, D, E, f0, K0, 8, data[15]);
/* j=16...31 */
subRound(E, A, B, C, D, f16, K1, 7, data[7]);
subRound(D, E, A, B, C, f16, K1, 6, data[4]);
subRound(C, D, E, A, B, f16, K1, 8, data[13]);
subRound(B, C, D, E, A, f16, K1, 13, data[1]);
subRound(A, B, C, D, E, f16, K1, 11, data[10]);
subRound(E, A, B, C, D, f16, K1, 9, data[6]);
subRound(D, E, A, B, C, f16, K1, 7, data[15]);
subRound(C, D, E, A, B, f16, K1, 15, data[3]);
subRound(B, C, D, E, A, f16, K1, 7, data[12]);
subRound(A, B, C, D, E, f16, K1, 12, data[0]);
subRound(E, A, B, C, D, f16, K1, 15, data[9]);
subRound(D, E, A, B, C, f16, K1, 9, data[5]);
subRound(C, D, E, A, B, f16, K1, 11, data[2]);
subRound(B, C, D, E, A, f16, K1, 7, data[14]);
subRound(A, B, C, D, E, f16, K1, 13, data[11]);
subRound(E, A, B, C, D, f16, K1, 12, data[8]);
/* j=32...47 */
subRound(D, E, A, B, C, f32, K2, 11, data[3]);
subRound(C, D, E, A, B, f32, K2, 13, data[10]);
subRound(B, C, D, E, A, f32, K2, 6, data[14]);
subRound(A, B, C, D, E, f32, K2, 7, data[4]);
subRound(E, A, B, C, D, f32, K2, 14, data[9]);
subRound(D, E, A, B, C, f32, K2, 9, data[15]);
subRound(C, D, E, A, B, f32, K2, 13, data[8]);
subRound(B, C, D, E, A, f32, K2, 15, data[1]);
subRound(A, B, C, D, E, f32, K2, 14, data[2]);
subRound(E, A, B, C, D, f32, K2, 8, data[7]);
subRound(D, E, A, B, C, f32, K2, 13, data[0]);
subRound(C, D, E, A, B, f32, K2, 6, data[6]);
subRound(B, C, D, E, A, f32, K2, 5, data[13]);
subRound(A, B, C, D, E, f32, K2, 12, data[11]);
subRound(E, A, B, C, D, f32, K2, 7, data[5]);
subRound(D, E, A, B, C, f32, K2, 5, data[12]);
/* j=48...63 */
subRound(C, D, E, A, B, f48, K3, 11, data[1]);
subRound(B, C, D, E, A, f48, K3, 12, data[9]);
subRound(A, B, C, D, E, f48, K3, 14, data[11]);
subRound(E, A, B, C, D, f48, K3, 15, data[10]);
subRound(D, E, A, B, C, f48, K3, 14, data[0]);
subRound(C, D, E, A, B, f48, K3, 15, data[8]);
subRound(B, C, D, E, A, f48, K3, 9, data[12]);
subRound(A, B, C, D, E, f48, K3, 8, data[4]);
subRound(E, A, B, C, D, f48, K3, 9, data[13]);
subRound(D, E, A, B, C, f48, K3, 14, data[3]);
subRound(C, D, E, A, B, f48, K3, 5, data[7]);
subRound(B, C, D, E, A, f48, K3, 6, data[15]);
subRound(A, B, C, D, E, f48, K3, 8, data[14]);
subRound(E, A, B, C, D, f48, K3, 6, data[5]);
subRound(D, E, A, B, C, f48, K3, 5, data[6]);
subRound(C, D, E, A, B, f48, K3, 12, data[2]);
/* j=64...79 */
subRound(B, C, D, E, A, f64, K4, 9, data[4]);
subRound(A, B, C, D, E, f64, K4, 15, data[0]);
subRound(E, A, B, C, D, f64, K4, 5, data[5]);
subRound(D, E, A, B, C, f64, K4, 11, data[9]);
subRound(C, D, E, A, B, f64, K4, 6, data[7]);
subRound(B, C, D, E, A, f64, K4, 8, data[12]);
subRound(A, B, C, D, E, f64, K4, 13, data[2]);
subRound(E, A, B, C, D, f64, K4, 12, data[10]);
subRound(D, E, A, B, C, f64, K4, 5, data[14]);
subRound(C, D, E, A, B, f64, K4, 12, data[1]);
subRound(B, C, D, E, A, f64, K4, 13, data[3]);
subRound(A, B, C, D, E, f64, K4, 14, data[8]);
subRound(E, A, B, C, D, f64, K4, 11, data[11]);
subRound(D, E, A, B, C, f64, K4, 8, data[6]);
subRound(C, D, E, A, B, f64, K4, 5, data[15]);
subRound(B, C, D, E, A, f64, K4, 6, data[13]);
AA = A;
BB = B;
CC = C;
DD = D;
EE = E;
/* ' */
A = ctx->digest[0];
B = ctx->digest[1];
C = ctx->digest[2];
D = ctx->digest[3];
E = ctx->digest[4];
/* j=0...15 */
subRound(A, B, C, D, E, f64, KK0, 8, data[5]);
subRound(E, A, B, C, D, f64, KK0, 9, data[14]);
subRound(D, E, A, B, C, f64, KK0, 9, data[7]);
subRound(C, D, E, A, B, f64, KK0, 11, data[0]);
subRound(B, C, D, E, A, f64, KK0, 13, data[9]);
subRound(A, B, C, D, E, f64, KK0, 15, data[2]);
subRound(E, A, B, C, D, f64, KK0, 15, data[11]);
subRound(D, E, A, B, C, f64, KK0, 5, data[4]);
subRound(C, D, E, A, B, f64, KK0, 7, data[13]);
subRound(B, C, D, E, A, f64, KK0, 7, data[6]);
subRound(A, B, C, D, E, f64, KK0, 8, data[15]);
subRound(E, A, B, C, D, f64, KK0, 11, data[8]);
subRound(D, E, A, B, C, f64, KK0, 14, data[1]);
subRound(C, D, E, A, B, f64, KK0, 14, data[10]);
subRound(B, C, D, E, A, f64, KK0, 12, data[3]);
subRound(A, B, C, D, E, f64, KK0, 6, data[12]);
/* j=16...31 */
subRound(E, A, B, C, D, f48, KK1, 9, data[6]);
subRound(D, E, A, B, C, f48, KK1, 13, data[11]);
subRound(C, D, E, A, B, f48, KK1, 15, data[3]);
subRound(B, C, D, E, A, f48, KK1, 7, data[7]);
subRound(A, B, C, D, E, f48, KK1, 12, data[0]);
subRound(E, A, B, C, D, f48, KK1, 8, data[13]);
subRound(D, E, A, B, C, f48, KK1, 9, data[5]);
subRound(C, D, E, A, B, f48, KK1, 11, data[10]);
subRound(B, C, D, E, A, f48, KK1, 7, data[14]);
subRound(A, B, C, D, E, f48, KK1, 7, data[15]);
subRound(E, A, B, C, D, f48, KK1, 12, data[8]);
subRound(D, E, A, B, C, f48, KK1, 7, data[12]);
subRound(C, D, E, A, B, f48, KK1, 6, data[4]);
subRound(B, C, D, E, A, f48, KK1, 15, data[9]);
subRound(A, B, C, D, E, f48, KK1, 13, data[1]);
subRound(E, A, B, C, D, f48, KK1, 11, data[2]);
/* j=32...47 */
subRound(D, E, A, B, C, f32, KK2, 9, data[15]);
subRound(C, D, E, A, B, f32, KK2, 7, data[5]);
subRound(B, C, D, E, A, f32, KK2, 15, data[1]);
subRound(A, B, C, D, E, f32, KK2, 11, data[3]);
subRound(E, A, B, C, D, f32, KK2, 8, data[7]);
subRound(D, E, A, B, C, f32, KK2, 6, data[14]);
subRound(C, D, E, A, B, f32, KK2, 6, data[6]);
subRound(B, C, D, E, A, f32, KK2, 14, data[9]);
subRound(A, B, C, D, E, f32, KK2, 12, data[11]);
subRound(E, A, B, C, D, f32, KK2, 13, data[8]);
subRound(D, E, A, B, C, f32, KK2, 5, data[12]);
subRound(C, D, E, A, B, f32, KK2, 14, data[2]);
subRound(B, C, D, E, A, f32, KK2, 13, data[10]);
subRound(A, B, C, D, E, f32, KK2, 13, data[0]);
subRound(E, A, B, C, D, f32, KK2, 7, data[4]);
subRound(D, E, A, B, C, f32, KK2, 5, data[13]);
/* j=48...63 */
subRound(C, D, E, A, B, f16, KK3, 15, data[8]);
subRound(B, C, D, E, A, f16, KK3, 5, data[6]);
subRound(A, B, C, D, E, f16, KK3, 8, data[4]);
subRound(E, A, B, C, D, f16, KK3, 11, data[1]);
subRound(D, E, A, B, C, f16, KK3, 14, data[3]);
subRound(C, D, E, A, B, f16, KK3, 14, data[11]);
subRound(B, C, D, E, A, f16, KK3, 6, data[15]);
subRound(A, B, C, D, E, f16, KK3, 14, data[0]);
subRound(E, A, B, C, D, f16, KK3, 6, data[5]);
subRound(D, E, A, B, C, f16, KK3, 9, data[12]);
subRound(C, D, E, A, B, f16, KK3, 12, data[2]);
subRound(B, C, D, E, A, f16, KK3, 9, data[13]);
subRound(A, B, C, D, E, f16, KK3, 12, data[9]);
subRound(E, A, B, C, D, f16, KK3, 5, data[7]);
subRound(D, E, A, B, C, f16, KK3, 15, data[10]);
subRound(C, D, E, A, B, f16, KK3, 8, data[14]);
/* j=64...79 */
subRound(B, C, D, E, A, f0, KK4, 8, data[12]);
subRound(A, B, C, D, E, f0, KK4, 5, data[15]);
subRound(E, A, B, C, D, f0, KK4, 12, data[10]);
subRound(D, E, A, B, C, f0, KK4, 9, data[4]);
subRound(C, D, E, A, B, f0, KK4, 12, data[1]);
subRound(B, C, D, E, A, f0, KK4, 5, data[5]);
subRound(A, B, C, D, E, f0, KK4, 14, data[8]);
subRound(E, A, B, C, D, f0, KK4, 6, data[7]);
subRound(D, E, A, B, C, f0, KK4, 8, data[6]);
subRound(C, D, E, A, B, f0, KK4, 13, data[2]);
subRound(B, C, D, E, A, f0, KK4, 6, data[13]);
subRound(A, B, C, D, E, f0, KK4, 5, data[14]);
subRound(E, A, B, C, D, f0, KK4, 15, data[0]);
subRound(D, E, A, B, C, f0, KK4, 13, data[3]);
subRound(C, D, E, A, B, f0, KK4, 11, data[9]);
subRound(B, C, D, E, A, f0, KK4, 11, data[11]);
T = ctx->digest[1] + D + CC;
ctx->digest[1] = ctx->digest[2] + E + DD;
ctx->digest[2] = ctx->digest[3] + A + EE;
ctx->digest[3] = ctx->digest[4] + B + AA;
ctx->digest[4] = ctx->digest[0] + C + BB;
ctx->digest[0] = T;
}
#if 1
#ifndef EXTRACT_UCHAR
#define EXTRACT_UCHAR(p) (*(word8 *)(p))
#endif
#define STRING2INT(s) ((((((EXTRACT_UCHAR(s+3) << 8) \
| EXTRACT_UCHAR(s+2)) << 8) \
| EXTRACT_UCHAR(s+1)) << 8) \
| EXTRACT_UCHAR(s))
#else
word32 STRING2INT(word8 * s)
{
word32 r;
int i;
for (i = 0, r = 0; i < 4; i++)
r = (r << 8) | s[3-i];
return r;
}
#endif
static void ripemd_block(struct ripemd_ctx *ctx, word8 * block)
{
word32 data[RIPEMD_DATALEN];
int i;
/* Update block count */
if (!++ctx->count_l)
++ctx->count_h;
/* Endian independent conversion */
for (i = 0; i < RIPEMD_DATALEN; i++, block += 4)
data[i] = STRING2INT(block);
ripemd_transform(ctx, data);
}
void ripemd_update(struct ripemd_ctx *ctx, word8 * buffer, word32 len)
{
if (ctx->index) { /* Try to fill partial block */
unsigned left = RIPEMD_DATASIZE - ctx->index;
if (len < left) {
memmove(ctx->block + ctx->index, buffer, len);
ctx->index += len;
return; /* Finished */
} else {
memmove(ctx->block + ctx->index, buffer, left);
ripemd_block(ctx, ctx->block);
buffer += left;
len -= left;
}
}
while (len >= RIPEMD_DATASIZE) {
ripemd_block(ctx, buffer);
buffer += RIPEMD_DATASIZE;
len -= RIPEMD_DATASIZE;
}
if ((ctx->index = len))
/* This assignment is intended */
/* Buffer leftovers */
memmove(ctx->block, buffer, len);
}
/* Final wrapup - pad to RIPEMD_DATASIZE-byte boundary with the bit pattern
1 0* (64-bit count of bits processed, MSB-first) */
void ripemd_final(struct ripemd_ctx *ctx)
{
word32 data[RIPEMD_DATALEN];
int i;
int words;
i = ctx->index;
/* Set the first char of padding to 0x80. This is safe since there is
always at least one byte free */
ctx->block[i++] = 0x80;
/* Fill rest of word */
for (; i & 3; i++)
ctx->block[i] = 0;
/* i is now a multiple of the word size 4 */
words = i >> 2;
for (i = 0; i < words; i++)
data[i] = STRING2INT(ctx->block + 4 * i);
if (words > (RIPEMD_DATALEN - 2)) { /* No room for length in this block.
Process it and
* pad with another one */
for (i = words; i < RIPEMD_DATALEN; i++)
data[i] = 0;
ripemd_transform(ctx, data);
for (i = 0; i < (RIPEMD_DATALEN - 2); i++)
data[i] = 0;
} else
for (i = words; i < RIPEMD_DATALEN - 2; i++)
data[i] = 0;
/* Theres 512 = 2^9 bits in one block */
data[RIPEMD_DATALEN - 1] =
(ctx->count_h << 9) | (ctx->count_l >> 23);
data[RIPEMD_DATALEN - 2] = (ctx->count_l << 9) | (ctx->index << 3);
ripemd_transform(ctx, data);
}
void ripemd_digest(struct ripemd_ctx *ctx, word8 * s)
{
int i;
for (i = 0; i < RIPEMD_DIGESTLEN; i++) {
*s++ = ctx->digest[i];
*s++ = 0xff & (ctx->digest[i] >> 8);
*s++ = 0xff & (ctx->digest[i] >> 16);
*s++ = 0xff & ctx->digest[i] >> 24;
}
}
==============0A892AD219C72790D51B9FE5==
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 01 Aug 2000 08:29:16 GMT
Subject: Re: Small block ciphers
>
>Mack wrote:
>
>> >Mack wrote:
>> >
>> >> But if we use a 12 bit key we now have 8 equations in
>> >> 12 variables. This is obviously not soluble with only one
>> >> ciphertext. If each nonlinear term is a 'variable' we now have
>> >> 4095 unknowns. This would require at least 512 pairs.
>> >> Since the maximum is 256 pairs it can't be solved under
>> >> this assumption.
>> >
>> >On what basis can/should one regard each non-linear term as a
>> >(independent) variable? Further, there can be non-linearity of
>> >different nature, so that a 'general' treatment of solutions may not
>> >be practical, I suppose. It seems also to be not clear with your
>> >'solvability with only one ciphertext'. The opponent is normally
>> >assumed to have quite a lot more materials to work with.
>>
>>
>> Who said that each non-linear term could be treated as an
>> 'independent' 'variable'?
>
>I took out of the context of your sentence that's an independent
>variable. If 'dependent' variable, what role do these play in your
>argument, which apparently depends on the count of variables
>with respect to the number of equations? Perhaps you could
>elaborate your proper argument in some details (maybe with an
>'analogous' example) so that others may unambiguously
>understand? Thanks.
>
>M. K. Shen
>
Let see an actual example.
This is rather long and uses ANF.
It is rather simple but it shows the principle.
This can be expanded to any number of bits T.
B = bits of block size
K = bits of key size.
T = B + K
The number of terms is equal to 2^T.
The number of equations is B
Obviously this is impractical for large T.
It also illustrates how a non-linear term can
be assumed to be a variable. It shows
how some pairs are better than others.
Finally it shows an example of a 'cipher'
that is weak and can be solved with
a carefully chosen ciphertext for certain
weak keys. Even though my 'theory'
says that we shouldn't be able to find
the key.
To make this easy I will use a 2 bit block size.
We will do this with a 2 bit key.
ok lets say we have a table of 2 bit permutations.
The key selects the permutation we will use.
There are 24 possible permutations.
00 = 0 1 2 3
01 = 1 0 2 3
02 = 0 2 1 3
03 = 2 0 1 3
04 = 2 1 0 3
05 = 1 2 0 3
06 = 0 1 3 2
07 = 1 0 3 2
08 = 0 2 3 1
09 = 2 0 3 1
10 = 2 1 3 0
11 = 1 2 3 0
12 = 0 3 1 2
13 = 1 3 0 2
14 = 0 3 2 1
15 = 2 3 0 1
16 = 2 3 1 0
17 = 1 3 2 0
18 = 3 0 1 2
19 = 3 1 0 2
20 = 3 0 2 1
21 = 3 2 0 1
22 = 3 2 1 0
23 = 3 1 2 0
with a two bit key we only have four permutations
available.
Selected at random (flipping coins)
Starting over if first two flips are both head (one).
0 = 22 = 3 2 1 0
1 = 03 = 2 0 1 3
2 = 11 = 1 2 3 0
3 = 21 = 3 2 0 1
We can then write out the equations
input bits AB
key bits CD
output bits EF
A^B is A XOR B (lowest precedent)
AB is A AND B (highest precedent)
0 = 3 2 1 0
E = 1^A
F = 1^B
1 = 2 0 1 3
E = 1^A^B
F = A
2 = 1 2 3 0
E = A^B
F = 1^B
3 = 3 2 0 1
E = 1^A
F = 1^A^B
The final equations of E and F are (I think this is correct it was done by
hand)
E = (1^C^D^CD)(1^A) ^ (D^CD)(1^A^B) ^ (C^CD)(A^B) ^ CD(1^A)
E = (1^C^D)(1^A) ^ (D^CD) ^ (D^CD)(A^B) ^ (C^CD)(A^B)
E = 1^C^D ^ (1^C^D)A ^ D^CD ^ (C^D)(A^B)
E = 1^C^CD ^ A^AC^AD ^ (C^D)A ^ (C^D)B
E = 1^C^CD ^ BC ^BD ^A
F = (1^C^D^CD)(1^B) ^ (D^CD)A ^ (C^CD)(1^B) ^ CD(1^A^B)
F = (1^D)(1^B) ^ AD ^ CD ^ BCD
F = 1 ^ D ^ B ^ BD ^ AD ^ CD ^ BCD
The input selected at random (coin flipping) is 0
The key is 3
The output will be 3
This gives
E=1 = 1^C^CD
F=1 = 1^D^CD
Note that in this step we can assume G=CD giving
E=1 = 1^C^G
F=1 = 1^D^G
which yeilds C=D
since the system is degenerate we cannot do better with one text
This gives us an expression of the inputs and outputs in reduced form
E= 1^A
F= 1^B^AC
A second input selected at random (coin flipping) is 3
The output will be 1
E=0 = 1^C^CD^C^D^1 = D^CD
F=1 = 1^D^1^D^D^CD^CD = D
Now with this iinput we can solve even without the first equations.
Here again we can assume G=CD
E=0 = D^G
F=1 = D
so
G=1 = CD = C
the key is three.
Now for a three bit key example.
0 = 00 = 0 1 2 3
1 = 01 = 1 0 2 3
2 = 08 = 0 2 3 1
3 = 10 = 2 1 3 0
4 = 13 = 1 3 0 2
5 = 16 = 2 3 1 0
6 = 18 = 3 0 1 2
7 = 21 = 3 2 0 1
These were carefully chosen
and it is not possible to find the
whole key from one pair.
Finally another three bit example
0 = 00 = 0 1 2 3
1 = 01 = 1 0 2 3
2 = 03 = 2 0 1 3
3 = 08 = 0 2 3 1
4 = 10 = 2 1 3 0
5 = 13 = 1 3 0 2
6 = 16 = 2 3 1 0
7 = 18 = 3 0 1 2
In this case if we have a carefully
chosen pair we can determine the key
with only one pair.
The possible choices are
key input output
7 0 3
3 1 2
5 2 0
3 3 1
In this case we have a low probability
pair that adds information. Similar
to the impossible differential attack.
But this only works for three 'weak'
keys and four specific pairs.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Small block ciphers
Date: Tue, 01 Aug 2000 10:49:27 +0200
Boris Kazak wrote:
> The difference is that stream ciphers have Internal State, and so
> their security has little to do with the block size. Arrange for a
> 32-bit
> cipher the ability to propagate its Internal State (e.g. a simple
> counter)
> and see the dramatic increase in security.
> BTW, in my opinion this will not be a 32-bit cipher any more...
In my opinion it is indeed quite strange that this idea has not been
popular till the present. I did employ though a combination of
stream and block encryption techniques in one of my humble
designs.
M. K. Shen
==========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 01 Aug 2000 08:42:44 GMT
Subject: Re: PRNG cryptoanalysis
>Hello everybody,
>I'd like to know if there is any site around dealing with cryptoanalysis
>of two common pseudo-random number generators known as "linear
>congruential" (maybe the easiest one around) and "linear feedback shift
>register" (or LFSR).
>I found many sites dealing with related theory and applications but none
>dealing with cryptoanalysis. :(
>Thank you in advance.
>
> Corrado Galdini
>
>
The Blum-Blum-Shub paper showed that the LCG generator was
weak.
The LFSR in its simplest form outputs its state as its output.
Various mechanisms have been invented to overcome this
drawback.
Both of these generators fail various statistical tests.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: What is DES3mCBCMACi64pPKCS5?
Date: 1 Aug 2000 01:50:01 -0700
David Hopwood <[EMAIL PROTECTED]> wrote:
> Mark Wooding wrote:
> > I'm not terribly keen on the idea of MACing the ciphertext: it violates
> > the 'Horton principle' that you should validate the *meaning* of what's
> > being said as closely as possible.
>
> ISTR reading an analysis of IPsec that said that MACing the ciphertext
> (which is what IPsec does) cannot be less secure than MACing the plaintext,
> although I can't remember whether that was proven or not.
As far as I know, David Hopwood's statement is about right,
but it has some important caveats.
The map D_k : Ciphertexts -> Plaintexts must be a true function,
i.e., it cannot depend on any unauthenticated side information
beyond the current ciphertext. For instance, compression could
well void the security warranty if it depends on some adaptive
dictionary built dynamically from previous cleartext (as, e.g.,
Lempel-Ziv compression does). And, you have to be sure that the
decryption key you use is authenticated, too!
I guess one reasonable conclusion to draw from this observation
is that you should always authenticate the plaintext and not take
any chances; another reasonable conclusion to draw is to vow to
be sure to never rely on any unauthenticated side information.
It's not clear to me which is the ``right'' viewpoint.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: ripemd-160 implementation
Date: 1 Aug 2000 08:55:44 GMT
Nikos Mavroyanopoulos <[EMAIL PROTECTED]> wrote:
> I attach a ripemd-160 implementation based on a public domain sha-1
> implementation. This is the same code used in mhash library.
Next time you want to give out some source code, please don't post it to
sci.crypt. And at the very least please don't post it three times.
There are newsgroups for posting sources. If you ask me, the best idea
is to post an announcement to appropriate groups giving a URI for the
actual code so that people who are interested can fetch it. It's not as
if free web space is hard to come by.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Elliptic Curves encryption
Date: 1 Aug 2000 02:06:46 -0700
DJohn37050 <[EMAIL PROTECTED]> wrote:
> Complexity of code is another advantage of ECC over alternatives, in my mind.
> No secret primes means no secret prime code.
>
> Almost ALL the complexity is in picking a good curve and NIST has given 15.
> Even if you want to use your own curve, it can be audited publicly by others to
> meet all current known security requirements.
How is this any different than (Z/pZ) based cryptosystems?
After all, IPSEC has picked a number of good Diffie-Hellman primes
and published them. Even if you want to use your own prime, it can
be audited publicly by others to meet all current known security
requirements (publish a proof of primality + factorization of p-1).
I must admit I can't see any difference here between elliptic curve
or Z/pZ. Surely I am missing something; consider this a request for
enlightenment...
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
