PureBasic Forums - English

Posted: **Tue Jul 15, 2003 5:52 pm**

;
; RC4 for PB by Pille, 16.07.2003 - Rev 2
;

;
; RC4 is a stream cipher designed by Rivest for RSA
; Data Security (now RSA Security). It is a variable
; key-size stream cipher with byte-oriented operations.
; The algorithm is based on the use of a random 
; permutation. Analysis shows that the period of the
; cipher is overwhelmingly likely to be greater than 
; 10^100. Eight to sixteen machine operations are required
; per output byte, and the cipher can be expected to run
; very quickly in software. Independent analysts have
; scrutinized the algorithm and it is considered secure. 
;


Procedure.s RC4(Inp.s, Key.s)
  ;encoded.s = RC4("Message", "Password")
  ;decoded.s = RC4(encoded, "Password")
  
  Dim S.w(255)
  Dim K.w(255)
  i.l=0: j.l=0: t.l=0: x.l=0
  temp.w=0: Y.w=0
  Outp.s=""

    For i = 0 To 255
        S(i) = i
    Next

    j = 1
    For i = 0 To 255
        If j > Len(key) 
            j = 1
        EndIf
        K(i) = Asc(Mid(key, j, 1))
        j = j + 1
    Next i

    j = 0
    For i = 0 To 255
        j = (j + S(i) + K(i)) & 255
        temp = S(i)
        S(i) = S(j)
        S(j) = temp
    Next i

    i = 0
    j = 0
    For x = 1 To Len(inp)
        i = (i + 1) & 255
        j = (j + S(i)) & 255
        temp = S(i)
        S(i) = S(j)
        S(j) = temp
        t = (S(i) + (S(j) & 255)) & 255
        Y = S(t)
        Outp = Outp + Chr(Asc(Mid(inp, x, 1))!Y)
    Next
  ProcedureReturn Outp
EndProcedure



Message.s = "I'm a secret string!" 
Key.s = "I'm the key!" 

text.s = "Plaintext: " + Message + chr(13) 
text = text + "Key: " + Key + chr(13) + chr(13) 
text = text + "RC4 Encoded: " + RC4(Message,Key) + chr(13) 
text = text + "RC4 Decoded: " + RC4(RC4(Message,Key),Key) + chr(13) 

MessageRequester("RC4 Test:",text,0)

Pay attention if you try to handle a String with Chr(0) - Strings in PB are 0 terminated. I try to improve the procedure - Thanks to Rings for this advice.

Posted: **Wed Jul 16, 2003 3:56 pm**

Suggestions.

Use a=b & 255 instead of a=mod(b,256) for greater speed.

Also, the key setup algorithm used here is quite fast. This is good and bad. Good because it saves processing time, but bad because it allows thousands of key setups to be tried every second. So, unless you have a long password (>8 characters say) it is possible to crack the code by brute force application of all possible passwords.

Posted: **Wed Jul 16, 2003 5:41 pm**

Hi,

thanks for the & 255 tip - I changed it in the code above

I agree, bruteforcing RC4 is easy if you use a too short password - but so is MD5, SHA etc. It depends how you use it

I have written a RC4Mem procedure to avoid the '0-terminatd-string-bug' - If you have any idea how to improve this code, let me know.

Code: Select all

; 
; RC4Mem for PB by Pille, 15.07.2003 
; Special Thanks to Rings 
; 

; 
; RC4 is a stream cipher designed by Rivest for RSA 
; Data Security (now RSA Security). It is a variable 
; key-size stream cipher with byte-oriented operations. 
; The algorithm is based on the use of a random 
; permutation. Analysis shows that the period of the 
; cipher is overwhelmingly likely to be greater than 
; 10^100. Eight to sixteen machine operations are required 
; per output byte, and the cipher can be expected to run 
; very quickly in software. Independent analysts have 
; scrutinized the algorithm and it is considered secure. 
; 


Procedure.l RC4Mem(Mem.l, memLen.l, Key.s) 
  ;RC4Mem(*MemoryBuffer.l, MomeryLength.l, Key.s) 
    
  Dim S.w(255) 
  Dim K.w(255) 
  i.l=0: j.l=0: t.l=0: x.l=0 
  temp.w=0: Y.w=0 
  Outp.s="" 

    For i = 0 To 255 
        S(i) = i 
    Next 

    j = 1 
    For i = 0 To 255 
        If j > Len(key) 
            j = 1 
        EndIf 
        K(i) = Asc(Mid(key, j, 1)) 
        j = j + 1 
    Next i 

    j = 0 
    For i = 0 To 255 
        j = (j + S(i) + K(i)) & 255 
        temp = S(i) 
        S(i) = S(j) 
        S(j) = temp 
    Next i 

    i = 0 
    j = 0 
    For x = 0 To memLen-1 
        i = (i + 1) & 255
        j = (j + S(i)) & 255
        temp = S(i) 
        S(i) = S(j) 
        S(j) = temp 
        t = (S(i) + (S(j) & 255)) & 255
        Y = S(t) 
        PokeB(Mem+x, PeekB(Mem+x)!Y) 
    Next 
  ProcedureReturn Mem 
EndProcedure 




;--------------------------------------------- 
; params 
; 

; Message length 
MsgLen.l=14

; Message Bin 
Mem.l=AllocateMemory(1,MsgLen) 
PokeB(Mem,Asc("H")) 
PokeB(Mem+1,Asc("e")) 
PokeB(Mem+2,Asc("l")) 
PokeB(Mem+3,Asc("l")) 
PokeB(Mem+4,Asc("o")) 
PokeB(Mem+5,Asc(" ")) 
PokeB(Mem+6,#Null) 
PokeB(Mem+7,0)
PokeB(Mem+8,Asc("W")) 
PokeB(Mem+9,Asc("o")) 
PokeB(Mem+10,Asc("r")) 
PokeB(Mem+11,Asc("l")) 
PokeB(Mem+12,Asc("d")) 
PokeB(Mem+13,Asc("!")) 

; Key 
Key.s = "0 Test" 




;--------------------------------------------- 
; test 1 
; 
debug RC4Mem(Mem,MsgLen,Key) 

For i.l=0 To msgLen-1 
  debug Chr(PeekB(mem+i)) 
next 

debug RC4Mem(Mem,MsgLen,Key) 

For i.l=0 To msgLen-1 
  debug Chr(PeekB(mem+i)) 
next 

;--------------------------------------------- 
; test 2 
; 

debug RC4Mem(RC4Mem(Mem,MsgLen,Key),MsgLen,Key) 

For i.l=0 To msgLen-1 
  debug Chr(PeekB(mem+i)) 
next

Posted: **Fri Jan 14, 2005 11:55 pm**

> RC4 for PB by Pille, 16.07.2003 - Rev 2

The strings created by this code are different to what Paul's RC4 lib creates.
So which is the actual true RC4 encryption then -- yours, or Paul's?

Shouldn't they create the same strings, if they both use the same key?

Posted: **Sat Jan 15, 2005 12:47 am**

I am wondering that as well

If there's a vb code counterpart to this code that produces the same, you'd be my hero.

Also, is there a way to determine if the key is invalid, like returns an error message of sorts?

Posted: **Sat Jan 15, 2005 1:58 am**

If there's a vb code counterpart to this code that produces the same, you'd be my hero.

Couldnâ€™t you just make a PB DLL that you can call from VB to encrypt, decrypt the sting? I have a DLL that calls Paulâ€™s RC4 function in VB for passwords stored in setup files or the registry.

Posted: **Sat Jan 15, 2005 2:15 am**

@PB
Can you post some code that shows the output is not the same?

If I look at the hex output of both, it looks the same to me...

Code: Select all

Key.s = "0 Test"

;Use with above procedure
test.s="This is a test"
Result=RC4Mem(@test,Len(test),Key)
For tmp=1 To Len(test)
  h$+RSet(Hex(Asc(Mid(test,tmp,1))),2,"0")
Next
Debug h$

;RC4Lib
test.s="This is a test"
Debug Left(CryptString(test,Key),Len(test)*2)

@Shannara
You cannot determine if a key is valid or invalid because the key is not stored in the encrypted data.
Just like XOR'ing data, the right key will change the data back, a wrong key will create garbage.

@Beach
Not sure if you know but a DLL of the RC4Lib was released the same time the RC4Lib was released. (available in the DLL section on http://www.pureproject.net) No need to "wrap" the RC4Lib functions.

Posted: **Sat Jan 15, 2005 2:40 am**

Not sure if you know but a DLL of the RC4Lib was released the same time the RC4Lib was released.

I did see it... but I thought it would be an added benefit to add extra information to the 'key' inside the DLL so that only my DLL and the correct key would decrypt the string. It all started over beer and wings with my .NET friend who challenged this method for storing passwords. His argument was that anyone who had the 'key' and the encrypted string could use any RC4 method to see the decrypted password... So, inside the DLL, I added:

key = key + "<extra suff>"

I looked at the DLL in a hex editor and I did not see the additional text. Would this not further complicate discovering the decrypted string? I'm a total noob to RC4 or any other crypting methods... :roll:

EDIT: Dohh! I did not look hard enough in the hex... I found my extra stuff in there. But hey, if someone has the DLL then its a mute point anyway.

Posted: **Sat Jan 15, 2005 3:24 am**

Beach wrote:
If there's a vb code counterpart to this code that produces the same, you'd be my hero.
Couldnâ€™t you just make a PB DLL that you can call from VB to encrypt, decrypt the sting? I have a DLL that calls Paulâ€™s RC4 function in VB for passwords stored in setup files or the registry.

It could but it would be slower then native vb code to call the dll (open, call function, close) like VB does to any non activex dll

And especially when I have to do upwards close to 100 a second...

I currently use AES for both vb client/server and been looking for a purecode equivilent in pb, but unable to find any (this was mentioned earlier). So if there was a pb solution, I would switch over.

Right now, AES returns a invalid key if the string passed to be decrypted is invalid. If the return only returned garbage and there was no way to tell it is garbage, then .. well..

Posted: **Sat Jan 15, 2005 2:54 pm**

> Can you post some code that shows the output is not the same?

Sure. BTW, I thought earlier that I misunderstood, but I was correct -- Pille's
procedure and your lib can return different results... depending on the text.
Below is an example. The name of the person in the code is a friend of mine,
and I use his name a lot when testing text functions. If I replace his name
with any other text, then both RC4 routines seem to work... it's almost as if
his name is jinxed or something?

Anyway, run this code, and you'll see the
following different outputs:

Code: Select all

; Different results!  :)
Pille's procedure = 959A50602752DBC832
Paul's RC4 lib    = 959A50602752DBC8003200

Code: Select all

Procedure.s RC4(Inp.s, Key.s)
  ;encoded.s = RC4("Message", "Password")
  ;decoded.s = RC4(encoded, "Password")
  
  Dim s.w(255)
  Dim k.w(255)
  i.l=0: j.l=0: t.l=0: x.l=0
  temp.w=0: Y.w=0
  Outp.s=""
  
  For i = 0 To 255
    s(i) = i
  Next
  
  j = 1
  For i = 0 To 255
    If j > Len(Key)
      j = 1
    EndIf
    k(i) = Asc(Mid(Key, j, 1))
    j = j + 1
  Next i
  
  j = 0
  For i = 0 To 255
    j = (j + s(i) + k(i)) & 255
    temp = s(i)
    s(i) = s(j)
    s(j) = temp
  Next i
  
  i = 0
  j = 0
  For x = 1 To Len(Inp)
    i = (i + 1) & 255
    j = (j + s(i)) & 255
    temp = s(i)
    s(i) = s(j)
    s(j) = temp
    t = (s(i) + (s(j) & 255)) & 255
    Y = s(t)
    Outp = Outp + Chr(Asc(Mid(Inp, x, 1))!Y)
  Next
  ProcedureReturn Outp
EndProcedure

t$="[edited]" : p$="password"

a$=RC4(t$,p$)
For tmp=1 To Len(a$)
  h$+RSet(Hex(Asc(Mid(a$,tmp,1))),2,"0")
Next
Debug h$ ; Pille's procedure.
Debug CryptString(t$,p$) ; Paul's lib.

Posted: **Sat Jan 15, 2005 3:07 pm**

[quote="PB"][/quote]

It has to do with 0 values that often occur in encryption/hash functions and the behaviour that 0s terminate a string.

If you look here

Code: Select all

Outp = Outp + Chr(Asc(Mid(Inp, x, 1))!Y)

and add a

Code: Select all

 Debug Asc(Mid(Inp, x, 1))!Y

then you will see that the outp string doesn't take 0 values into account.

Posted: **Sat Jan 15, 2005 3:13 pm**

Code: Select all

; Different results!  :)
Pille's procedure = 959A50602752DBC832
Paul's RC4 lib    = 959A50602752DBC8003200

BTW, the correct result should be

Code: Select all

959A50602752DBC800328

as the last value from Paul's lib is the string terminator (streaming encryption produces output as long as the input).

Posted: **Sat Jan 15, 2005 3:24 pm**

> Pay attention if you try to handle a String with Chr(0)

Strings can't contain Chr(0) -- as you said -- so why would there be a need
to pay attention to something that can never occur in the first place? 8O

Posted: **Sat Jan 15, 2005 3:33 pm**

PB wrote:> Pay attention if you try to handle a String with Chr(0)

Strings can't contain Chr(0) -- as you said -- so why would there be a need
to pay attention to something that can never occur in the first place? 8O

Of course it can occur. The encryption routine works with values (edit: numbers is the better word), not with characters and generate any value between 0 and 255, depending on which operations the routine does and the message & key selected.

Code: Select all

Outp = Outp + Chr(Asc(Mid(Inp, x, 1))!Y)

fails to return a proper string when Asc(Mid(Inp, x, 1))!Y = 0, as Outp = Outp + Chr(0) is the same as Outp=Outp. You are missing the value 0.

For that reason, any enc/ded routine I use returns/expects the hexa representation, not a chr()'d string.

Posted: **Sat Jan 15, 2005 3:37 pm**

> The encryption routine works with values [snip]

I didn't mean the encryption routine -- I meant the original string to be
encrypted. That can't contain a 0-byte, so I was wondering why we had
to be careful. Now I see where the actual problem lies -- and it appears
that Paul's lib is therefore returning the correct encrypted values.

PureBasic Forums - English

RC4

RC4

Re: RC4

Re: RC4

Re: RC4

Re: RC4

Re: RC4

Re: RC4