RC4

Share your advanced PureBasic knowledge/code with the community.
Pille
New User
New User
Posts: 7
Joined: Thu Jul 03, 2003 11:29 pm

RC4

Post by Pille »

Code: Select all

;
; 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.
Last edited by Pille on Wed Jul 16, 2003 5:18 pm, edited 3 times in total.
User avatar
geoff
Enthusiast
Enthusiast
Posts: 128
Joined: Sun Apr 27, 2003 12:01 am
Location: Cornwall UK
Contact:

Post by geoff »

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.
Pille
New User
New User
Posts: 7
Joined: Thu Jul 03, 2003 11:29 pm

Post by Pille »

Hi,

thanks for the & 255 tip - I changed it in the code above :D
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
PB
PureBasic Expert
PureBasic Expert
Posts: 7581
Joined: Fri Apr 25, 2003 5:24 pm

Re: RC4

Post by PB »

> 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?
I compile using 5.31 (x86) on Win 7 Ultimate (64-bit).
"PureBasic won't be object oriented, period" - Fred.
Shannara
Addict
Addict
Posts: 1808
Joined: Thu Oct 30, 2003 11:19 pm
Location: Emerald Cove, Unformed

Post by Shannara »

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?
Beach
Enthusiast
Enthusiast
Posts: 677
Joined: Mon Feb 02, 2004 3:16 am
Location: Beyond the sun...

Post by Beach »

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.
-Beach
User avatar
Paul
PureBasic Expert
PureBasic Expert
Posts: 1243
Joined: Fri Apr 25, 2003 4:34 pm
Location: Canada
Contact:

Post by Paul »

@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.
Beach
Enthusiast
Enthusiast
Posts: 677
Joined: Mon Feb 02, 2004 3:16 am
Location: Beyond the sun...

Post by Beach »

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. :)
Last edited by Beach on Sat Jan 15, 2005 3:36 am, edited 1 time in total.
-Beach
Shannara
Addict
Addict
Posts: 1808
Joined: Thu Oct 30, 2003 11:19 pm
Location: Emerald Cove, Unformed

Post by Shannara »

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..
PB
PureBasic Expert
PureBasic Expert
Posts: 7581
Joined: Fri Apr 25, 2003 5:24 pm

Re: RC4

Post by PB »

> 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? :lol: 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.
Last edited by PB on Thu Mar 17, 2005 11:17 am, edited 1 time in total.
I compile using 5.31 (x86) on Win 7 Ultimate (64-bit).
"PureBasic won't be object oriented, period" - Fred.
Max.²
Enthusiast
Enthusiast
Posts: 175
Joined: Wed Jul 28, 2004 8:38 am

Re: RC4

Post by Max.² »

[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.
Last edited by Max.² on Sat Jan 15, 2005 3:14 pm, edited 1 time in total.
Max.²
Enthusiast
Enthusiast
Posts: 175
Joined: Wed Jul 28, 2004 8:38 am

Post by Max.² »

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).
PB
PureBasic Expert
PureBasic Expert
Posts: 7581
Joined: Fri Apr 25, 2003 5:24 pm

Re: RC4

Post by PB »

> 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
I compile using 5.31 (x86) on Win 7 Ultimate (64-bit).
"PureBasic won't be object oriented, period" - Fred.
Max.²
Enthusiast
Enthusiast
Posts: 175
Joined: Wed Jul 28, 2004 8:38 am

Re: RC4

Post by Max.² »

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.
Last edited by Max.² on Sat Jan 15, 2005 3:39 pm, edited 1 time in total.
PB
PureBasic Expert
PureBasic Expert
Posts: 7581
Joined: Fri Apr 25, 2003 5:24 pm

Re: RC4

Post by PB »

> 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.
I compile using 5.31 (x86) on Win 7 Ultimate (64-bit).
"PureBasic won't be object oriented, period" - Fred.
Post Reply