4. Hilfe bei C-Code Analyse (MD4)

Hilfe bei C-Code Analyse (MD4)

  • K

    Hey,
    ich brauche dringend eure Hilfe, da ich leider ein wenig auf dem Schlauch stehe.
    Ich hab einige Erfahrung in C, bin jedoch nie wirklich in die bitweise Verschiebung eingetaucht, weswegen ich jetz die Probleme habe.
    Es geht um folgendes:
    Für die Uni soll ich im Rahmen eines Projekts eine MD4-Hashfunktion auf der Cell-Architektur (also als SIMD-Variante) implementieren.
    Den Ablauf von MD4 hab ich soweit verstanden, nun muss ich blos den Quelltext genau analysieren, um Ansätze für die Umsetzung in SIMD zu finden;
    und da scheitere ich in meinem Beispielquelltext (aus RFC1320) an den bitweisen verschiebungen, weil ich nicht weis was die alle machen 😞
    Ich poste euch erstmal den Quelltext und markiere dann alle Stellen bei welchen ich hilfe brauch und die ich nicht verstehe.

    Ich habe alles mir unverständliche Fett geschrieben.

    #include <stdlib.h>

#include <sys/types.h>
#include <string.h>
#include "./libmd/libmd-0.3/md4.h"

typedef unsigned char *POINTER;
typedef u_int16_t UINT2;
typedef u_int32_t UINT4;

#define PROTO_LIST(list) list

/* Constants for MD4Transform routine.
 */
#define S11 3
#define S12 7
#define S13 11
#define S14 19
#define S21 3
#define S22 5
#define S23 9
#define S24 13
#define S31 3
#define S32 9
#define S33 11
#define S34 15

static void MD4Transform PROTO_LIST ((UINT4 [4], const unsigned char [64]));
static void Encode PROTO_LIST
  ((unsigned char *, UINT4 *, unsigned int));
static void Decode PROTO_LIST
  ((UINT4 *, const unsigned char *, unsigned int));

static unsigned char PADDING[64] = {
  0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

/* F, G and H are basic MD4 functions.
 */
#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))

/* ROTATE_LEFT rotates x left n bits.
 */
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))

/* FF, GG and HH are transformations for rounds 1, 2 and 3 */
/* Rotation is separate from addition to prevent recomputation */
#define FF(a, b, c, d, x, s) { \
    (a) += F ((b), (c), (d)) + (x); \
    (a) = ROTATE_LEFT ((a), (s)); \
  }
#define GG(a, b, c, d, x, s) { \
    (a) += G ((b), (c), (d)) + (x) + (UINT4)0x5a827999; \
    (a) = ROTATE_LEFT ((a), (s)); \
  }
#define HH(a, b, c, d, x, s) { \
    (a) += H ((b), (c), (d)) + (x) + (UINT4)0x6ed9eba1; \
    (a) = ROTATE_LEFT ((a), (s)); \
  }

/* MD4 initialization. Begins an MD4 operation, writing a new context.
 */
void MD4Init (context)
MD4_CTX *context;                                        /* context */
{
  context->count[0] = context->count[1] = 0;

  /* Load magic initialization constants.
   */
  context->state[0] = 0x67452301;
  context->state[1] = 0xefcdab89;
  context->state[2] = 0x98badcfe;
  context->state[3] = 0x10325476;
}

/* MD4 block update operation. Continues an MD4 message-digest
     operation, processing another message block, and updating the
     context.
 */
void MD4Update (context, input, inputLen)
MD4_CTX *context;                                        /* context */
const unsigned char *input;                                /* input block */
unsigned int inputLen;                     /* length of input block */
{
  unsigned int i, index, partLen;

  /* Compute number of bytes mod 64 */
 [b]index = (unsigned int)((context->count[0] >> 3) & 0x3F);[/b]

  /* Update number of bits */
 [b] if ((context->count[0] += ((UINT4)inputLen << 3))
      < ((UINT4)inputLen << 3)) [/b]
    context->count[1]++;
 [b]  context->count[1] += ((UINT4)inputLen >> 29); [/b]

  partLen = 64 - index;
  /* Transform as many times as possible.
   */
  if (inputLen >= partLen) {
    memcpy
      ((POINTER)&context->buffer[index], (POINTER)input, partLen);
    MD4Transform (context->state, context->buffer);

    for (i = partLen; i + 63 < inputLen; i += 64)
      MD4Transform (context->state, &input[i]);

    index = 0;
  }
  else
    i = 0;

  /* Buffer remaining input */
  memcpy
    ((POINTER)&context->buffer[index], (POINTER)&input[i],
     inputLen-i);
}

/* MD4 finalization. Ends an MD4 message-digest operation, writing the
     the message digest and zeroizing the context.
 */
void MD4Final (digest, context)
unsigned char digest[16];                         /* message digest */
MD4_CTX *context;                                        /* context */
{
  unsigned char bits[8];
  unsigned int index, padLen;

  /* Save number of bits */
  Encode (bits, context->count, 8);

  /* Pad out to 56 mod 64.
   */
  index = (unsigned int)((context->count[0] >> 3) & 0x3f);
 [b] padLen = (index < 56) ? (56 - index) : (120 - index); [/b]
  MD4Update (context, PADDING, padLen);

  /* Append length (before padding) */
  MD4Update (context, bits, 8);
  /* Store state in digest */
  Encode (digest, context->state, 16);

  /* Zeroize sensitive information.
   */
  memset ((POINTER)context, 0, sizeof (*context));
}

/* MD4 basic transformation. Transforms state based on block.
 */
static void MD4Transform (state, block)
UINT4 state[4];
const unsigned char block[64];
{
  UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16];

  Decode (x, block, 64);

  /* Round 1 */
  FF (a, b, c, d, x[ 0], S11); /* 1 */
  FF (d, a, b, c, x[ 1], S12); /* 2 */
  FF (c, d, a, b, x[ 2], S13); /* 3 */
  FF (b, c, d, a, x[ 3], S14); /* 4 */
  FF (a, b, c, d, x[ 4], S11); /* 5 */
  FF (d, a, b, c, x[ 5], S12); /* 6 */
  FF (c, d, a, b, x[ 6], S13); /* 7 */
  FF (b, c, d, a, x[ 7], S14); /* 8 */
  FF (a, b, c, d, x[ 8], S11); /* 9 */
  FF (d, a, b, c, x[ 9], S12); /* 10 */
  FF (c, d, a, b, x[10], S13); /* 11 */
  FF (b, c, d, a, x[11], S14); /* 12 */
  FF (a, b, c, d, x[12], S11); /* 13 */
  FF (d, a, b, c, x[13], S12); /* 14 */
  FF (c, d, a, b, x[14], S13); /* 15 */
  FF (b, c, d, a, x[15], S14); /* 16 */

  /* Round 2 */
  GG (a, b, c, d, x[ 0], S21); /* 17 */
  GG (d, a, b, c, x[ 4], S22); /* 18 */
  GG (c, d, a, b, x[ 8], S23); /* 19 */
  GG (b, c, d, a, x[12], S24); /* 20 */
  GG (a, b, c, d, x[ 1], S21); /* 21 */
  GG (d, a, b, c, x[ 5], S22); /* 22 */
  GG (c, d, a, b, x[ 9], S23); /* 23 */
  GG (b, c, d, a, x[13], S24); /* 24 */
  GG (a, b, c, d, x[ 2], S21); /* 25 */
  GG (d, a, b, c, x[ 6], S22); /* 26 */
  GG (c, d, a, b, x[10], S23); /* 27 */
  GG (b, c, d, a, x[14], S24); /* 28 */
  GG (a, b, c, d, x[ 3], S21); /* 29 */
  GG (d, a, b, c, x[ 7], S22); /* 30 */
  GG (c, d, a, b, x[11], S23); /* 31 */
  GG (b, c, d, a, x[15], S24); /* 32 */

  /* Round 3 */
  HH (a, b, c, d, x[ 0], S31); /* 33 */
  HH (d, a, b, c, x[ 8], S32); /* 34 */
  HH (c, d, a, b, x[ 4], S33); /* 35 */
  HH (b, c, d, a, x[12], S34); /* 36 */
  HH (a, b, c, d, x[ 2], S31); /* 37 */
  HH (d, a, b, c, x[10], S32); /* 38 */
  HH (c, d, a, b, x[ 6], S33); /* 39 */
  HH (b, c, d, a, x[14], S34); /* 40 */
  HH (a, b, c, d, x[ 1], S31); /* 41 */
  HH (d, a, b, c, x[ 9], S32); /* 42 */
  HH (c, d, a, b, x[ 5], S33); /* 43 */
  HH (b, c, d, a, x[13], S34); /* 44 */
  HH (a, b, c, d, x[ 3], S31); /* 45 */
  HH (d, a, b, c, x[11], S32); /* 46 */
  HH (c, d, a, b, x[ 7], S33); /* 47 */
  HH (b, c, d, a, x[15], S34); /* 48 */

  state[0] += a;
  state[1] += b;
  state[2] += c;
  state[3] += d;

  /* Zeroize sensitive information.
   */
  memset ((POINTER)x, 0, sizeof (x));
}

/* Encodes input (UINT4) into output (unsigned char). Assumes len is
     a multiple of 4.
 */
static void Encode (output, input, len)
unsigned char *output;
UINT4 *input;
unsigned int len;
{
  unsigned int i, j;

  for (i = 0, j = 0; j < len; i++, j += 4) {
[b]  output[j] = (unsigned char)(input[i] & 0xff);
    output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
    output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
    output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);[b]
  }
}

/* Decodes input (unsigned char) into output (UINT4). Assumes len is
     a multiple of 4.
 */
static void Decode (output, input, len)

UINT4 *output;
const unsigned char *input;
unsigned int len;
{
  unsigned int i, j;

  for (i = 0, j = 0; j < len; i++, j += 4)
    output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) |
      (((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24);
}

int main(int argc, char** argv)
{

char* passwd = "test1";

int len = strlen(passwd);
printf("length %d\n", len);
int idx = 0;

char nt_pw[2*len];

for(idx=0;idx<len;idx++)
{
	nt_pw[2*idx] = passwd[idx];
	nt_pw[2*idx+1] = 0;
}

printf("%s\n", nt_pw);

unsigned char nt_hpw[21];
MD4_CTX context;
MD4Init(&context);
MD4Update(&context, nt_pw, 2*len);
MD4Final(nt_hpw, &context);

for(idx=0;idx<21;idx++)
{	printf("  %x  ", nt_hpw[idx]);}

printf("\n");
for(idx=0;idx<10;idx++)
{	printf("%d\t", nt_pw[idx]);}

printf("\n", nt_hpw);

return 0;}

    Im Prinzip sind es wirklich immer die Shiftoperatoren, bei welchen ich nicht verstehe warum sie gemacht werden.
    (Wenn es * bzw / sein soll, warum dann nicht direkt?)
    Vielen Dank schonmal, Jonathan

    PS: Sorry aber irgendwie funktioniert es nicht mit den [cpp]-Tags, sodass ichs leier nur als Code markieren kann.

    0
  • M

    Das Problem ist das man nicht weiß was context ist und was überhaupt in count steht aber ich werde mal versuchen dir die erste deiner markierten Zeilen zu erklären. Das gute ist der Komentar sagt eigentlich schon alles.

    /* Compute number of bytes mod 64 */
 index = (unsigned int)((context->count[0] >> 3) & 0x3F);

    Angenommen: In count steht die Anzahl von Bits die für irgendetwas gezählt werden.

    Also nimm z.B: 10000100 = 132 wenn Du die Anzahl nun in Bytes haben möchtest musst du durch 8 teilen (= 16).

    Shiftest Du die Zahl nun um 3 (context->count[0] >> 3) nach rechts dann verschwinden sozusagen die letzten 3 Ziffern und es bleibt nur noch 10000 was der Zahl 16 entspricht.

    oder: 10000 binär entspricht 16 dezimal --> wenn du die zahl einzeln shiftest das heißt immer die letzte 0 wegnimmst dann wird sie jeweils halbiert.

    Ok nun der zweite Teil: Hier verwenden die eine sog. Bitmaske 0x3f ist hexadezimal und repräsentiert die binäre zahl 111 1111 (3 = 3 einsen, f = 15 = 4 einsen) das ist die Zahl 2⁶ - 1 = 63
    Das wird mit einem & verknüpft. (nur wenn beide bits eine haben wird in das ergebnis auch eine eins übernommen).

    Das heißt nun das nur und auch nur genau die letzen 7 bits aus dem geschifteten übernommen werden.

    Also deine bitmaske sieht mit 32 bit so aus
    000000000000000000000000000 111 1111 und eine schon geshiftete Zahl z.B so
    000000000000000000000000001 010 1001 dann ist das Ergebnis des &
    000000000000000000000000000 010 1001

    Das entspricht einer Modulo 64 operation da alle 2er potenzen < 2⁷ durch 64 ohne Rest zu teilen sind.

    Ich hoffe ich konnte helfen

    Gruß,
    vom muli

    0
Anmelden zum Antworten