It is currently Fri Nov 15, 2019 2:56 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 42 posts ]  Go to page 1, 2, 3  Next
Author Message
 Post subject: RC4
PostPosted: Tue Jul 15, 2003 5:52 pm 
Offline
New User
New User

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

Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Wed Jul 16, 2003 3:56 pm 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Sun Apr 27, 2003 12:01 am
Posts: 128
Location: Cornwall UK
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.


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Wed Jul 16, 2003 5:41 pm 
Offline
New User
New User

Joined: Thu Jul 03, 2003 11:29 pm
Posts: 7
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:
;
; 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


Top
 Profile  
Reply with quote  
 Post subject: Re: RC4
PostPosted: Fri Jan 14, 2005 11:55 pm 
Offline
PureBasic Expert
PureBasic Expert

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


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat Jan 15, 2005 12:47 am 
Offline
Addict
Addict
User avatar

Joined: Thu Oct 30, 2003 11:19 pm
Posts: 1808
Location: Emerald Cove, Unformed
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?


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat Jan 15, 2005 1:58 am 
Offline
Enthusiast
Enthusiast
User avatar

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


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat Jan 15, 2005 2:15 am 
Offline
PureBasic Expert
PureBasic Expert
User avatar

Joined: Fri Apr 25, 2003 4:34 pm
Posts: 918
Location: Canada
@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:
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.


Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat Jan 15, 2005 2:40 am 
Offline
Enthusiast
Enthusiast
User avatar

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

_________________
-Beach


Last edited by Beach on Sat Jan 15, 2005 3:36 am, edited 1 time in total.

Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat Jan 15, 2005 3:24 am 
Offline
Addict
Addict
User avatar

Joined: Thu Oct 30, 2003 11:19 pm
Posts: 1808
Location: Emerald Cove, Unformed
Beach wrote:
Quote:
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..


Top
 Profile  
Reply with quote  
 Post subject: Re: RC4
PostPosted: Sat Jan 15, 2005 2:54 pm 
Offline
PureBasic Expert
PureBasic Expert

Joined: Fri Apr 25, 2003 5:24 pm
Posts: 7581
> 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:
; Different results!  :)
Pille's procedure = 959A50602752DBC832
Paul's RC4 lib    = 959A50602752DBC8003200

Code:
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.

_________________
I compile using 5.31 (x86) on Win 7 Ultimate (64-bit).
"PureBasic won't be object oriented, period" - Fred.


Last edited by PB on Thu Mar 17, 2005 11:17 am, edited 1 time in total.

Top
 Profile  
Reply with quote  
 Post subject: Re: RC4
PostPosted: Sat Jan 15, 2005 3:07 pm 
Offline
Enthusiast
Enthusiast

Joined: Wed Jul 28, 2004 8:38 am
Posts: 175
[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:
Outp = Outp + Chr(Asc(Mid(Inp, x, 1))!Y)

and add a
Code:
 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.

Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: Sat Jan 15, 2005 3:13 pm 
Offline
Enthusiast
Enthusiast

Joined: Wed Jul 28, 2004 8:38 am
Posts: 175
Code:
; Different results!  :)
Pille's procedure = 959A50602752DBC832
Paul's RC4 lib    = 959A50602752DBC8003200


BTW, the correct result should be
Code:
959A50602752DBC800328
as the last value from Paul's lib is the string terminator (streaming encryption produces output as long as the input).


Top
 Profile  
Reply with quote  
 Post subject: Re: RC4
PostPosted: Sat Jan 15, 2005 3:24 pm 
Offline
PureBasic Expert
PureBasic Expert

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


Top
 Profile  
Reply with quote  
 Post subject: Re: RC4
PostPosted: Sat Jan 15, 2005 3:33 pm 
Offline
Enthusiast
Enthusiast

Joined: Wed Jul 28, 2004 8:38 am
Posts: 175
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:
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.

Top
 Profile  
Reply with quote  
 Post subject: Re: RC4
PostPosted: Sat Jan 15, 2005 3:37 pm 
Offline
PureBasic Expert
PureBasic Expert

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


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 42 posts ]  Go to page 1, 2, 3  Next

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye