SB/ARM MD5

[JRS]

Charles,

I'm not sure if your checking your e-mail or not but I discovered that the SB version of MD5 fails to give the correct results on ARM based processors. The embedded controller and my Galaxy Tab 2 table both return the same incorrect results. I sent you the login info to the embedded device if you need something to debug on. I was really worried that the older version of SB used in the embedded device was flawed.

John

[Charles Pegge]

Hi John,

Yes I am just getting accustomed to the BabelBuster terminal. What we to need to do is check all the functions and logical operations in the MD5 program, to see how each performs. I will create another test program to play with.

PS:

I've found that signed integers are not allowed to overflow. They are clamped to 0x7fffffff. when doing arithmetic. This may be down to GCC compiling for the ARM processor

[JRS]

Thanks Charles for having a peek.

Let me know what I can do to help nail this.

On a positive note, it could have been a CSI SB issue and in that case things would have been pretty grim. (little or no chance of a fix from them)

[Charles Pegge]

Our host has been offline for a few hours now, so I continued offline. Perhaps you could check it on your Android, John. I'm using a longer test string, which should yield a hash code of D17..D9F

I've marked the changes in bold here:

' MD5 Hash Generator for ScriptBasic
' standard RFC1321
' http://en.wikipedia.org/wiki/MD5
' Charles E V Pegge 10:42 15/06/2013



function leftrotate(v,p)
  local bp,ba,co,cq,bi,x,y
  bp=1
  ba[31]=0
  x=0xffffffff and v
  for co=0 to 31
    bi=x and bp
    cq=(co+p) % 32
    if (bi<>0) then
      ba[cq]=1
    else
      ba[cq]=0
    end if
    bp = bp + bp
  next
  bp=1
  y=0
  for co=0 to 31
    if (ba[co]<>0) then
      y=y or bp
    end if
    bp = bp + bp
  next
  leftrotate=y
end function


function Top3Bits(v)
local m
m=0
if (v and 0x80000000) then
  m = m + 4
end if
if (v and 0x40000000) then
  m = m + 2
end if
if (v and 0x20000000) then
  m = m + 1
end if
Top3Bits=m
end function


function mkint4(v)
local a,b
b=0
if (v>=2147483648) then
  v=v-2147483648
  b=128
else
  b=0
end if
a=(v and 0xff000000)\0x1000000
mkint4=chr(v and 0xff) & chr((v and 0xff00)\0x100) & chr((v and 0xff0000)\0x10000) & chr(a + b)
'mkint4=chr(v and 0xff) & chr((v and 0xff00)\0x100) & chr((v and 0xff0000)\0x10000) & chr((v and 0xff000000)\0x1000000 )
end function


function cvint4(s)
local a,b
b=asc(mid(s,4,1))
if (b>=128) then
  b=b-128
  a=0x80000000
else
  a=0
end if
cvint4=asc(mid(s,1,1)) + asc(mid(s,2,1))*0x100 + asc(mid(s,3,1))*0x10000 + asc(mid(s,4,1))*0x1000000 or a
'cvint4=asc(mid(s,1,1)) + asc(mid(s,2,1))*0x100 + asc(mid(s,3,1))*0x10000 + asc(mid(s,4,1))*0x1000000
end function


function StringToHexString(s)
local t,i
t=""
for i=1 to 16
  t = t & right("0" & hex(asc(mid(s,i,1))),2)
next
StringToHexString=t
end function

' Use binary integer part of the sines of integers (Radians) as constants:
' for i from 0 to 63
'    K[ i ] := floor(abs(sin(i + 1)) × (2 pow 32))
' end for
' (Or just use the following table):
'

k[00]=0xd76aa478
k[01]=0xe8c7b756
k[02]=0x242070db
k[03]=0xc1bdceee
k[04]=0xf57c0faf
k[05]=0x4787c62a
k[06]=0xa8304613
k[07]=0xfd469501
k[08]=0x698098d8
k[09]=0x8b44f7af
k[10]=0xffff5bb1
k[11]=0x895cd7be
k[12]=0x6b901122
k[13]=0xfd987193
k[14]=0xa679438e
k[15]=0x49b40821
k[16]=0xf61e2562
k[17]=0xc040b340
k[18]=0x265e5a51
k[19]=0xe9b6c7aa
k[20]=0xd62f105d
k[21]=0x02441453
k[22]=0xd8a1e681
k[23]=0xe7d3fbc8
k[24]=0x21e1cde6
k[25]=0xc33707d6
k[26]=0xf4d50d87
k[27]=0x455a14ed
k[28]=0xa9e3e905
k[29]=0xfcefa3f8
k[30]=0x676f02d9
k[31]=0x8d2a4c8a
k[32]=0xfffa3942
k[33]=0x8771f681
k[34]=0x6d9d6122
k[35]=0xfde5380c
k[36]=0xa4beea44
k[37]=0x4bdecfa9
k[38]=0xf6bb4b60
k[39]=0xbebfbc70
k[40]=0x289b7ec6
k[41]=0xeaa127fa
k[42]=0xd4ef3085
k[43]=0x04881d05
k[44]=0xd9d4d039
k[45]=0xe6db99e5
k[46]=0x1fa27cf8
k[47]=0xc4ac5665
k[48]=0xf4292244
k[49]=0x432aff97
k[50]=0xab9423a7
k[51]=0xfc93a039
k[52]=0x655b59c3
k[53]=0x8f0ccc92
k[54]=0xffeff47d
k[55]=0x85845dd1
k[56]=0x6fa87e4f
k[57]=0xfe2ce6e0
k[58]=0xa3014314
k[59]=0x4e0811a1
k[60]=0xf7537e82
k[61]=0xbd3af235
k[62]=0x2ad7d2bb
k[63]=0xeb86d391

' r specifies the per-round shift amounts
'
r[00]=7
r[01]=12
r[02]=17
r[03]=22
r[04]=7
r[05]=12
r[06]=17
r[07]=22
r[08]=7
r[09]=12
r[10]=17
r[11]=22
r[12]=7
r[13]=12
r[14]=17
r[15]=22
r[16]=5
r[17]= 9
r[18]=14
r[19]=20
r[20]=5
r[21]= 9
r[22]=14
r[23]=20
r[24]=5
r[25]= 9
r[26]=14
r[27]=20
r[28]=5
r[29]= 9
r[30]=14
r[31]=20
r[32]=4
r[33]=11
r[34]=16
r[35]=23
r[36]=4
r[37]=11
r[38]=16
r[39]=23
r[40]=4
r[41]=11
r[42]=16
r[43]=23
r[44]=4
r[45]=11
r[46]=16
r[47]=23
r[48]=6
r[49]=10
r[50]=15
r[51]=21
r[52]=6
r[53]=10
r[54]=15
r[55]=21
r[56]=6
r[57]=10
r[58]=15
r[59]=21
r[60]=6
r[61]=10
r[62]=15
r[63]=21

function md5(message)
'
local a,b,c,d,e,f,g,nb,nd
local h0,h1,h2,h3
local i,w
local initial_len,new_len,offset,temp,new_message
'
initial_len=len(message)
new_len=0
offset=0
a=0
b=0
c=0
d=0
i=0
f=0
g=0
temp=0
'
' Initialize digest variables - simple count in nibbles:

h0 = 0x67452301
h1 = 0xefcdab89
h2 = 0x98badcfe
h3 = 0x10325476
'
for i=0 to 15
  w[ i]=0
next
'
' Pre-processing:
' append "1" bit to message    
' append "0" bits until message length in bits = 448 (mod 512) (56 bytes)
' append length mod (2^64) to message
'
new_len=initial_len+1
while ((new_len and 63)<>56)
  new_len = new_len + 1
wend
'

' message length bits quad
' initial_len>>29 == initial_len*8>>32, but avoids overflow.
new_message=message & chr(0x80) & string(new_len-initial_len-1,chr(0)) & mkint4(initial_len* & mkint4(0)
' mkint4(Top3Bits(initial_len))
'
' Process the message in successive 512-bit chunks:
' for each 512-bit chunk of message:
'
for offset=1 to new_len step 64
  'break chunk into sixteen 32-bit words w[j], 0 = j = 15
  for i = 0 to 15
    w[ i] = cvint4(mid(new_message,offset + i*4,4))
  next
   '
  'Initialize hash value for this chunk:
  a = h0
  b = h1
  c = h2
  d = h3
  '
  ' Main loop:
  '
  for i = 0 to 63
    if (i < 16) then
      nb=not(b)
      f = (b and c) or (nb and d)
      g = i
    elseif (i < 32) then
      nd=not(d)
      f = (d and b) or (nd and c)
      g = (5*i + 1) and 15
      ' mod 16
    elseif (i < 48) then
      f = b xor c xor d
      g = (3*i + 5) and 15
      ' mod 16        
    else
      nd=not(d)
      f = c xor (b or nd)
      g = (7*i) and 15
      ' mod 16
    end if
    temp = d
    d = c
    c = b
    x=leftrotate(a+f+k[ i ]+w[g],r[ i])
    b = b + x
    'b=b and 0xffffffff
   if (b>=4294967296) then
      b=b-4294967296
    end if
   a = temp
    'original d
  next
  'Add this chunk's hash to result so far:
  h0 = h0 + a
 if (h0>=4294967296) then
    h0=h0-4294967296
  end if
 h1 = h1 + b
 if (h1>=4294967296) then
    h1=h1-4294967296
  end if
 h2 = h2 + c
 if (h2>=4294967296) then
    h2=h2-4294967296
  end if
 h3 = h3 + d
 if (h3>=4294967296) then
    h3=h3-4294967296
  end if
next
' Output is in little-endian
md5=mkint4(h0) & mkint4(h1) & mkint4(h2) & mkint4(h3)
end function

' sppro = md5("ABC123")
' bb..56
 sppro = md5("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789")
' d174ab98d277d9f5a5611c2c9f419d9f

' PRINT info & "|"
FOR x = 1 TO LEN(sppro)
  hexchr = HEX(ASC(MID(sppro,x,1)))
  IF LEN(hexchr) = 1 THEN hexchr = "0" & hexchr
  PRINT hexchr
  ' PRINT hexchr & "|"
NEXT
PRINTNL
line input q

' END

' TEST CASES:
'

' MD5("")
' d41d8cd98f00b204e9800998ecf8427e

' MD5("The quick brown fox jumps over the lazy dog")
' 9e107d9d372bb6826bd81d3542a419d6

' MD5("The quick brown fox jumps over the lazy dog.")
' e4d909c290d0fb1ca068ffaddf22cbd0

' FROM RFC1321
'
' MD5 test suite:
' MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
' MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
' MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
' MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
' MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
' MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789")
' d174ab98d277d9f5a5611c2c9f419d9f
' MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890")
' 57edf4a22be3c955ac49da2e2107b67a



X

[JRS]

Charles,

Here are the results running on the SGT2 10.1 tablet. I don't think it returned the value your were expecting but it looks a lot closer. IMHO




John

[Charles Pegge]

Here is another one to try. I have rewritten the left-rotate, since there was a potential clamping from bp. So I have used a lookup table instead

rt[00]=0x1
rt[01]=0x2
rt[02]=0x4
rt[03]=0x8
rt[04]=0x10
rt[05]=0x20
rt[06]=0x40
rt[07]=0x80
rt[08]=0x100
rt[09]=0x200
rt[10]=0x400
rt[11]=0x800
rt[12]=0x1000
rt[13]=0x2000
rt[14]=0x4000
rt[15]=0x8000
rt[16]=0x10000
rt[17]=0x20000
rt[18]=0x40000
rt[19]=0x80000
rt[20]=0x100000
rt[21]=0x200000
rt[22]=0x400000
rt[23]=0x800000
rt[24]=0x1000000
rt[25]=0x2000000
rt[26]=0x4000000
rt[27]=0x8000000
rt[28]=0x10000000
rt[29]=0x20000000
rt[30]=0x40000000
rt[31]=0x80000000



function leftrotate(v,p)
  local co,cq,x,y
  x=v
  y=0
  if (x>=4294967296) then
    x=x-4294967296
  end if
  for co=0 to 31
    bi=x and rt[co]
    cq=(co+p) and 0x1f
    if (bi<>0) then
      y=y or rt[cq]
    end if
  next
  leftrotate=y
end function



X

[JRS]

This version returns the following:

00000080000000800000008000000080

[Charles Pegge]

Very strange! I'm checking this code on the standard SB / PC / Windows

Using modulus 32 instead of bitmask 31, in LeftRotate:

X

[JRS]

Same results as CP1.

[Charles Pegge]

Slight alteration. Also checking RT array.


X

[JRS]

Same as CP1 & CP2.

RT30: 40000000

[Charles Pegge]

converting all limit check values to float:

  while (x>=4294967296.0)
    x=x-4294967296.0
  wend


X

[JRS]

Same as CP1, CP2 and CP3.

No RT results.

[Peter]

Same results as CP1.
Same as CP1 & CP2.
Same as CP1, CP2 and CP3.

LOL      

[JRS]

You're not being helpful Peter. This is critical I get this working.