problem with DES (Data Encryption Standard)
shamil
is after decrypting it, it fails a [string match..] test with the
orginal one!! Below is an example of what I'm talking about. Any idea
why this is the case?
/sd
######## begin script #######
package require des
set text1 {mypassword}
set cryptedtext [DES::des -mode encode -key mykey $text1]
set text2 [DES::des -mode decode -key mykey $cryptedtext]
if {[string equal $text1 $text2]} {puts matched
} else {puts "No match even though $text1 = $text2"}
######### end script ########
# result:
No match even though mypassword = mypassword
Oscar Fuentes
Crypto algorithms usually require that the initial data must be given
in blocks of certain size. I can't remember the requirements for
block-mode DES, but doing
set text1 {mypasswordxxxxxx} # (16 characters)
returns matched, which suggests that 16 bytes are ok. (Check it in the
man pages).
This means you must pad the original text and un-pad the decrypted
text when they are not multiplies of the data block size required by the
algorithm.
--
Oscar
sleb...@gmail.com
If you try to use "mykey" as a -key for des you'll get an error. DES
requires an 8 byte key - exactly 8 bytes, no more, no less. So you'll
need to use something like "mykeyabc" for the -key.
Also, you need to understand that DES is a block cypher. It expects its
data to be multiples of 8 bytes. In this case "mypassword" is 6 bytes
short of 16 bytes. When I tested encrypting and decrypting "mypassword"
I found that the DES::des command will append null characters "\0" to
make it a multiple of 8 bytes. So it makes sense that $text1 and $text2
are not equal:
$text1 = "mypassword"
$text2 = "mypassword\0\0\0\0\0\0"
shamil
by DES
/sd
sleb...@gmail.com
It appears that DES automatically pads it with "\0" for you by default.
Personally I don't like this because:
1. "\0" is a valid, though non-printable ASCII character.
2. This makes it unfriendly to binary data.
3. I prefer to be in control of the padding. Specifically I prefer to
use 0xff as the padding character.
I developed the following snippet as a general purpose
padding-unpadding mechanism. It uses an escape character mechanism for
padding binary data so it doesn't matter if the padding character
exists in the original data.
Also, it ensures that character escapes are themselves aligned to the
block size so it also adds padding in the middle of the data in cases
where the 2 byte escape sequence crosses block boundries.
The final feature is that instead of a single padding character it
randomly selects from a list of padding characters (what can I say, I'm
paranoid). Hopefully this makes it harder to crack a given cypher.
The (quite long) code:
#############################################
# Implements byte padding for block based protocols
# thus converting them into stream capable protocols.
#############################################
###
# Randomly choose a list item
###
proc lrandom ls {
set len [llength $ls]
lindex $ls [expr {int(rand()*$len)}]
}
##
# Use this proc to define the escape character you
# want to use and the list of padding characters:
##
proc makemaps {escapeChar charList} {
global pad
# Chars used for padding (to be chosen at random):
set pad(chars) $charList
set pad(escape) $escapeChar
# Generate mapping table:
set i 1
set pad(map) [list $escapeChar ${escapeChar}[binary format c $i]]
foreach x $charList {
incr i
lappend pad(map) $x
lappend pad(map) $escapeChar$i
}
unset i
# Generate reverse mapping table:
set pad(unmap) ""
foreach {x y} $pad(map) {
lappend pad(unmap) $y
lappend pad(unmap) $x
}
foreach x $charList {
lappend pad(unmap) $x
lappend pad(unmap) {}
}
}
# My preferred escape character and set of
# padding characters
makemaps \252 {
\377 \376 \375 \374 \373 \372 \371 \370
\367 \366 \365 \364 \363 \362 \361 \360
}
##
# Make sure that data is a multiple of n:
##
proc pad {n data} {
global pad
set data [string map $pad(map) $data]
set ret ""
set nn [expr {$n-1}]
while {[string length $data] != 0} {
set x [string range $data 0 $nn]
if {[string index $x end] == "$pad(escape)"} {
set x [string range $x 0 end-1]
set data [string range $data $nn end]
} else {
set data [string range $data $n end]
}
set len [string length $x]
set r [expr {($n-($len%$n))%$n}]
for {} {$r > 0} {incr r -1} {
append x [lrandom $pad(chars)]
}
append ret $x
}
return $ret
}
##
# Convert padded data back to original form:
##
proc unpad {data} {
global pad
string map $pad(unmap) $data
}
### end script
An example of how to use the above pad/unpad commands with DES:
# Use [pad 8] since DES block size is 8 bytes:
set cryptedtext [DES::des -mode encode -key mykey [pad 8 $text1]]
set text2 [unpad [DES::des -mode decode -key mykey $cryptedtext]]
If you prefer "%" as the escape character and "x" as the padding
character:
% makemaps % x
% set foo [pad 8 "sexy"]
se%2yxxx
% unpad $foo
sexy
Since padding is done at the block level rather than the whole string
it is safe to process the padded data block by block. This is important
in cases where the data may be fragmented for example if getting the
data from a socket:
% set foo [pad 8 "the x factor"]
the %2 factorxxx
% set result [unpad [string range $foo 0 7]]
the x f
% append result [unpad [string range $foo 8 end]
actor
% set result
the x factor
Oscar Fuentes
> Oscar Fuentes wrote:
>> Crypto algorithms usually require that the initial data must be given
>> in blocks of certain size. I can't remember the requirements for
>> block-mode DES, but doing
>>
>> set text1 {mypasswordxxxxxx} # (16 characters)
>>
>> returns matched, which suggests that 16 bytes are ok. (Check it in the
>> man pages).
>>
>> This means you must pad the original text and un-pad the decrypted
>> text when they are not multiplies of the data block size required by the
>> algorithm.
>
> It appears that DES automatically pads it with "\0" for you by default.
> Personally I don't like this because:
[snip]
This is why I say the user must pad the data. The crypto algorithm
implementation must *not* pad the data. By padding the block on behalf
of the user, this DES implementation is doing too much, wich is the
same as saying it is doing the wrong thing.
[snip]
> I developed the following snippet as a general purpose
> padding-unpadding mechanism. It uses an escape character mechanism for
> padding binary data so it doesn't matter if the padding character
> exists in the original data.
The "standard" practice is to pad the last data block with a byte
whose value is the number of padding chars used. For instance, when
the last data block is 10 bytes long but the algorithm requires 16
bytes, you pad the block with 6 bytes with value 6. If the last block
has the required length, you add an extra block with 16 bytes with
value 16.
[snip]
--
Oscar
vinayak...@gmail.com
set text1 {mypassword} insted of this line I used as set text1
"mypassword"
try it.....
or else u can do like this also
set cryptedtext [DES::des -mode encode -key mykey -file <file_name>]
% package require des
0.8.1
% set text1 "mypassword"
mypassword
% set cryptedtext [DES::des -mode encode -key mykey $text1]
?ô☺ëÆ??? «?²
% set text2 [DES::des -mode decode -key mykey $cryptedtext]
mypassword
%
sleb...@gmail.com
> "sleb...@yahoo.com" <sleb...@gmail.com> writes:
>
> > Oscar Fuentes wrote:
> >> This means you must pad the original text and un-pad the decrypted
> >> text when they are not multiplies of the data block size required by the
> >> algorithm.
> >
> > padding-unpadding mechanism. It uses an escape character mechanism for
> > padding binary data so it doesn't matter if the padding character
> > exists in the original data.
>
> The "standard" practice is to pad the last data block with a byte
> whose value is the number of padding chars used. For instance, when
> the last data block is 10 bytes long but the algorithm requires 16
> bytes, you pad the block with 6 bytes with value 6. If the last block
> has the required length, you add an extra block with 16 bytes with
> value 16.
I considered that but it doesn't work well with a "stream" of data. For
example, with an 8 byte block, if I have in my stream the following:
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x11, 0xa5
I can never be certain if the string of 8, 0x08 signifies the end of
the previous packet in which case 0x11, 0xa5 is the beginning of a new
packet or if it is actually part of a single large packet. Worse is the
case where the previous packet was only one byte short in which case
the padding is a single 0x01. So unpadding requires intimate knowledge
of the structure of the packet of data.
Besides, I also wanted my padding character to be random ;-)
Oscar Fuentes
> Oscar Fuentes wrote:
>> The "standard" practice is to pad the last data block with a byte
>> whose value is the number of padding chars used. For instance, when
>> the last data block is 10 bytes long but the algorithm requires 16
>> bytes, you pad the block with 6 bytes with value 6. If the last block
>> has the required length, you add an extra block with 16 bytes with
>> value 16.
>
> I considered that but it doesn't work well with a "stream" of data.
Block-mode cyphers are meant to work on blocks, not streams (there is
a stream-mode DES, but I don't know if it is available on Tcl). That
is, on a block-mode cyphered message the number of bytes is a multiple
of the block length.
> For
> example, with an 8 byte block, if I have in my stream the following:
>
> 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x11, 0xa5
>
> I can never be certain if the string of 8, 0x08 signifies the end of
> the previous packet in which case 0x11, 0xa5 is the beginning of a new
> packet or if it is actually part of a single large packet. Worse is the
> case where the previous packet was only one byte short in which case
> the padding is a single 0x01. So unpadding requires intimate knowledge
> of the structure of the packet of data.
The only knowledge you need is the length of the block. (And to agree
with the other part the padding method).
> Besides, I also wanted my padding character to be random ;-)
I don't follow here. You mean that you want the padding character to
be user-defined, don't you? Using a random padding character has no
sense.
--
Oscar
sleb...@gmail.com
> "sleb...@yahoo.com" <sleb...@gmail.com> writes:
>
> > Oscar Fuentes wrote:
> >> The "standard" practice is to pad the last data block with a byte
> >> whose value is the number of padding chars used. For instance, when
> >
>
> Block-mode cyphers are meant to work on blocks, not streams (there is
> a stream-mode DES, but I don't know if it is available on Tcl). That
But that's what padding is for. To convert a "packet" of data in a
stream into multiples of bolck length. TCP sockets have the unfortunate
habbit of being heavily stream oriented and you can't rely on it to
send you a simple "packet" of data. The TCP packet carrying your
protocol "packet" will be fragmented. And sometimes you have no control
where TCP will chop up your "packet". I've succesfully used my code to
convert blowfish, aes and des to work on streams. All you need to do is
copy and paste ;-)
> > case where the previous packet was only one byte short in which case
> > the padding is a single 0x01. So unpadding requires intimate knowledge
> > of the structure of the packet of data.
>
> The only knowledge you need is the length of the block. (And to agree
> with the other part the padding method).
No, that's not enough information to work on. The protocol I'm using
uses a persistent connection to send and request data. Everything on
the socket is blowfish encrypted including the protocol's packet
delimiter. So without decrypting the packet I cannot know how long the
packet actually is. This means I don't actually know if the packet is
complete or not before decrypting. I cannot simply rely on timeouts
since multiple packets may be sent back to back. I cannot use [gets]
since even newlines are encrypted. So I needed robust padding mechanism
which allows me to decrypt and handle incomplete packets.
So back to the situation I described. If I see a string of 8, 0x08 how
sure am I that it is padding and not part of actual data. Even it it is
at appears at the end of recieved data I can't be sure that TCP did not
fragment the data and there is actually still some data left on the
network waiting to be read. This is what I mean when I say that the
unpadding code need to know the structure of the data I'm sending.
While this is easy enough to do I don't like mixing functionality. I
like my unpadding proc to only do unpadding and let my parser deal with
packet structure.
> > Besides, I also wanted my padding character to be random ;-)
>
> I don't follow here. You mean that you want the padding character to
> be user-defined, don't you? Using a random padding character has no
> sense.
The code I posted (which is now also available at
http://wiki.tcl.tk/binpad) selects random characters from a list of
characters to be the padding character. Obviously the list of
characters to choose from must contain less than 255 elements or you'll
run out of symbols. I usually use a list of 64 characters. The list of
characters to choose from is user defined using the [makemaps] command.
So for example if I define:
makemaps x {a b c d e 1 2 3 4 5}
then the packet will be padded by either a,b,c,d,e,1,2,3,4 or 5. Each
symbol have a 10% chance of being selected. If the padding character
exists in the original data then it will be escaped by a two byte
sequence in the form of:
<escape character><replacement symbol>
in the case above the escape character is "x".
For example, using the above mapping, if I run a string through the pad
command 3 times I'll get 3 different results:
% pad 8 "hello world"
hx6llo worlx5d13
% pad 8 "hello world"
hx6llo worlx5cca
% pad 8 "hello world"
hx6llo worlx5b42
That's what I mean by random: the padding character is selected at
random. And in this case the randomness is user defined. If for example
you don't want random padding characters simply use something like:
makemaps x a
which defines a padding character "a".
Oscar Fuentes
> Oscar Fuentes wrote:
>> >> The "standard" practice is to pad the last data block with a byte
>> >> whose value is the number of padding chars used. For instance, when
>> >
>> > I considered that but it doesn't work well with a "stream" of data.
>>
>> Block-mode cyphers are meant to work on blocks, not streams (there is
>> a stream-mode DES, but I don't know if it is available on Tcl). That
>
> But that's what padding is for. To convert a "packet" of data in a
> stream into multiples of bolck length. TCP sockets have the unfortunate
> habbit of being heavily stream oriented and you can't rely on it to
> send you a simple "packet" of data. The TCP packet carrying your
> protocol "packet" will be fragmented. And sometimes you have no control
> where TCP will chop up your "packet". I've succesfully used my code to
> convert blowfish, aes and des to work on streams. All you need to do is
> copy and paste ;-)
IMHO you are using a quite lax definition of stream. It is true that
data is transmitted as a stream, but when your program receives a TCP
packet, it is a stream no more. You have a number of bytes. The crypto
algorithm requires data on blocks of X bytes, so you slice your data
on such blocks. If the data you receive is not a multiple of X, the
remainder bytes are left waiting for next TCP packet. Of course you
need to know how to recognise the last block, but I can't see a
problem here: either you prepend the *whole* data length (in bytes,
blocks, wathever) or you flag the end of data somehow on the last
block.
>> > case where the previous packet was only one byte short in which case
>> > the padding is a single 0x01. So unpadding requires intimate knowledge
>> > of the structure of the packet of data.
>>
>> The only knowledge you need is the length of the block. (And to agree
>> with the other part the padding method).
>
> No, that's not enough information to work on. The protocol I'm using
> uses a persistent connection to send and request data. Everything on
> the socket is blowfish encrypted including the protocol's packet
> delimiter. So without decrypting the packet I cannot know how long the
> packet actually is. This means I don't actually know if the packet is
> complete or not before decrypting.
What is stopping you from decrypting a block you've received?
> I cannot simply rely on timeouts
> since multiple packets may be sent back to back. I cannot use [gets]
> since even newlines are encrypted. So I needed robust padding mechanism
> which allows me to decrypt and handle incomplete packets.
Once you have a block, you can decypher it. There is no need to wait
for next block. Neither is need for a "robust padding mechanism": if
you receive 8 bytes, you get 8 bytes of plaintext after deciphering,
unless it is the last block, in which case you have 8-padding bytes.
> So back to the situation I described. If I see a string of 8, 0x08 how
> sure am I that it is padding and not part of actual data.
Because the block itself (or a previous block) contains the number of
bytes expected or a marker signaling the last block?
[snip]
>> > Besides, I also wanted my padding character to be random ;-)
>>
>> I don't follow here. You mean that you want the padding character to
>> be user-defined, don't you? Using a random padding character has no
>> sense.
>
> The code I posted (which is now also available at
> http://wiki.tcl.tk/binpad)
[snip]
Although the system you use may work, the padding schema I've
described does not need to escape any characters (which is expensive
on large data chunks) and is much simpler.
--
Oscar
Pat Thoyts
[snip]
>Block-mode cyphers are meant to work on blocks, not streams (there is
>a stream-mode DES, but I don't know if it is available on Tcl). That
[snip]
cipher feedback (cfb)
The key still needs to be 8 bytes though. (or 56 bits really).
--
Pat Thoyts http://www.patthoyts.tk/
To reply, rot13 the return address or read the X-Address header.
PGP fingerprint 2C 6E 98 07 2C 59 C8 97 10 CE 11 E6 04 E0 B9 DD
sleb...@gmail.com
This is what I'm saying. You're saying exactly what I'm saying but
your're not getting what you're saying. I don't want to have to know
the "structure" of transmitted data while unpadding. Otherwise the
process would have to be:
puts $channel [encrypt [pad [construct $packet]]]
parse_and_unpad [decrypt [read $channel]]
ie. I would have to know where the last block is. Like I said. It is
not hard to do but I prefer to be able to do:
puts $channel [encrypt [pad [construct $packet]]]
parse [unpad [decrypt [read $channel]]]
because this way I only need to write the unpad function once and use
it for all my future projects. It doesn't care what the structure of
the packet is and where the last block of data on an individual packet
is.
> >> > case where the previous packet was only one byte short in which case
> >> > the padding is a single 0x01. So unpadding requires intimate knowledge
> >> > of the structure of the packet of data.
> >>
> >> The only knowledge you need is the length of the block. (And to agree
> >> with the other part the padding method).
> >
> > No, that's not enough information to work on. The protocol I'm using
> > uses a persistent connection to send and request data. Everything on
> > the socket is blowfish encrypted including the protocol's packet
> > delimiter. So without decrypting the packet I cannot know how long the
> > packet actually is. This means I don't actually know if the packet is
> > complete or not before decrypting.
>
> What is stopping you from decrypting a block you've received?
>
> Once you have a block, you can decypher it. There is no need to wait
> for next block. Neither is need for a "robust padding mechanism": if
> you receive 8 bytes, you get 8 bytes of plaintext after deciphering,
> unless it is the last block, in which case you have 8-padding bytes.
Aha. The catch is unless it is the last block. It's not decrypting
that's the problem but the unpadding. Which means my unpadding function
needs to parse the packet to find the last block. And that condition
will change depending on the protocol I use. Like I said, I prefer to
separate my functions for re-usability.
> > So back to the situation I described. If I see a string of 8, 0x08 how
> > sure am I that it is padding and not part of actual data.
>
> Because the block itself (or a previous block) contains the number of
> bytes expected or a marker signaling the last block?
Which means the unpadding function needs to know what the marker signal
is. Which is exactly what I don't want.
> [snip]
>
> >> > Besides, I also wanted my padding character to be random ;-)
> >>
> >> I don't follow here. You mean that you want the padding character to
> >> be user-defined, don't you? Using a random padding character has no
> >> sense.
> >
> > The code I posted (which is now also available at
> > http://wiki.tcl.tk/binpad)
> [snip]
>
> Although the system you use may work, the padding schema I've
> described does not need to escape any characters (which is expensive
> on large data chunks) and is much simpler.
Escapes are only expensive if they happen often. You'll notice that the
default set of padding characters I've chosen is in the range of 0x80 -
0xff which means that for ASCII based protocols it has the same
overhead compared to the schema you described, in fact in some cases
even less overhead (because I don't need to send a block full of
padding in case what I'm sending actually contains exact multiples of
block size).
This is also the reason I made my mapping configurable so that given a
protocol I simply choose padding characters which are statistically
rare.
Besides, I want my padding characters to be random.
sleb...@gmail.com
> Oscar Fuentes <osc...@telefonica.net> writes:
>
> [snip]
> >Block-mode cyphers are meant to work on blocks, not streams (there is
> >a stream-mode DES, but I don't know if it is available on Tcl). That
> [snip]
>
> cipher feedback (cfb)
>
> The key still needs to be 8 bytes though. (or 56 bits really).
Or cypher block chaining (cbc) which is supported along with cfb in
tcllib. Aslo supported by blowfish and aes in tcllib.
Twylite
> This is why I say the user must pad the data. The crypto algorithm
> implementation must *not* pad the data. By padding the block on behalf
> of the user, this DES implementation is doing too much, wich is the
> same as saying it is doing the wrong thing.
This is good advice. A crypto algorithm implementation _should_ reject
input data that is not a multiple of the block length.
> The "standard" practice is to pad the last data block with a byte
> whose value is the number of padding chars used. For instance, when
> the last data block is 10 bytes long but the algorithm requires 16
> bytes, you pad the block with 6 bytes with value 6. If the last block
> has the required length, you add an extra block with 16 bytes with
> value 16.
This isn't a great practice when working with binary data -- any binary
data a multiple of the block length that happens to end with the byte
0x01, for example, will be corrupted. In short, this padding scheme is
not reversible.
Another suggestion on this thread was to pad with 0xFF -- such a scheme
is also not reversible and would corrupt binary data.
There are three recognised standards for padding that are used in
conjunction with DES data enchiperment and/or MACing. They are defined
in ANSI X9 and ISO standards, and are:
(1) Pad with zero bits up to a multiple of the block length. This
scheme is not reversible.
(2) Pad with a single one bit, then with zero bits up to a multiple of
the block length. Note that the one bit is _always_ added, even if the
input data is already a multiple of the block length. This scheme is
reversible -- you can always remove the padding without possibility of
corrupting the original data.
(3) Add a block to the front of the input data, and it in encode the
length _in bits_ of the actual data. The encoding should be in big
endian format (least significant bit last, being the last bit of the
block, with leading zero bits before the MSB). Pad the input data with
zero bits to a multiple of the block length. Note that the length block
must be encrypted (or form part of the MAC) to protect it against
modification. This scheme is also reversible.
Padding scheme 2 is probably the most widely used (and easiest to use)
reversible padding scheme, and I would recommend it for most applications.
> ######## begin script #######
> package require des
> set text1 {mypassword}
> set cryptedtext [DES::des -mode encode -key mykey $text1]
> set text2 [DES::des -mode decode -key mykey $cryptedtext]
> if {[string equal $text1 $text2]} {puts matched
> } else {puts "No match even though $text1 = $text2"}
> ######### end script ########
A word of caution on TclLib's DES package: _always_ use "--" to force
the end of the options. It is entirely possible that your binary $text1
will start with a "-" and be interpreted as an option:
package require des
set mykey [binary format H* 0123456789ABCDEF]
set text1 "-password"
DES::des -mode encode -key $mykey $text1
-> bad option -password: must be one of -key mode filename
Here's a proc to add the padding:
proc pad80 {msgbin} {
return "${msgbin}\x80[string repeat \0 [expr { 7 - ([string length
$msgbin] % 8) }]]"
}
Regards,
Twylite
Darren New
> > bytes, you pad the block with 6 bytes with value 6. If the last block
> > has the required length, you add an extra block with 16 bytes with
> > value 16.
>
> This isn't a great practice when working with binary data -- any binary
> data a multiple of the block length that happens to end with the byte
> 0x01, for example, will be corrupted.
No, because it would be followed by a block of sixteen 16's. It's no
different than your #2 in this respect.
--
Darren New / San Diego, CA, USA (PST)
"What do you use for regression testing?"
".bash_history"