Re: Question about bit strength
- From: "Antony Clements" <antony.clements@xxxxxxxxxxxxxxx>
- Date: Thu, 14 Sep 2006 00:27:44 +1000
<snip>
First: strength<end snip>
Make good guesses about strength of an encryption soultion is not very
easy.
The algorithms used to derive the key and for actual encryption process
have to be formally and practically analysed to try to understand what
characteristics are to be expected or, better, can be proven.
If an attack exist that can lead to expose the secret factor (the key)
or recover all the encrypted data in given steps, the strength of the
algorithm is at most equal to the number of steps needed to break it;
however it can exist partial breaks that expose part of the content, or
works under some circumstances (weak keys, known plaintext, encryption
of multiple plaintexts with the same key, issues for amount of data to
encrypt due to the block size etc), that can reduce even further an
effort of compromise the security of data encrypted with this
algorithm, a much more strict quantification of strength should take in
account also those events.
As you correctly guessed in another post, it's rather pointless
dicussing on algorithms without having the real thing to analyse, so
what is usaully needed is a) the algorithm itself b) a working
implementation available under a license that reasonably allow people
to study it c) creating a momentum of interest for drive actually
qualified people to study it, that is not easy (prizes are not usually
a silver bullet to get people involved)
This is however not an easy process, i.e. AES contest involved a lot of
highly qualified man power (and computing power) to analyse the
algorithms submitted, moreover the process is not likely going to
terminate somewhere in the near future, you shold reasonably expect
anytime anyone come out with a new idea that make the algorithm
requires new tests (also if none of the proven properties is
falsified).
That's why most people desire standards: to stick with things that
undergone to the whidest possible amount of analysis.
Second: key
There is also another limiting factor to the strength of the
encryption: the attacker may try all the keys, that is a brute force
attack.
If we chose a bigger keyspace, we don't authomatically make the system
stronger, since if we allow 2^n keys but the encryption due to
algorithm's weakness can be broken in 2^m steps, with m<n, the overall
strength will be m.
Moreover, we need a secure algorithm to derive the n bit key from the
secret shared between sender and receiver (a password, a key file, a
challange-response event etc).
If we prove that the encryption algorithm cannot be broken in less than
2^n steps and that the key derivation can efficiently use the 2^n
keyspace, then we can prove that the system will have n bit strength
(if we cannot prove it, but also cannot break it, we can even say that
no attack is known for the algorithm in a n bit keyspace).
Third: speed
The speed you provided should be contextualised, I mean, it would be
useful to know that on a sistem with given specs your implementation
encrypt x bit of data in y seconds while another product uses z
seconds.
You should also specify if it is aimed to be a practical benchmark (so,
opening files, reading/writing to disk, testing for I/O errors) or a
benchmark between reference implementations, that usually keep data in
memory to avoid disk bottleneck and usually performs minimal checking.
finally some constructive questions and criticism, i'll try to answer them
all.
strength:
I created this method so that it would have to be tested using a full key,
with every possible combination from 8-64 for method 1 and 64-4096 for
method 2 using every character in the bit range bar the first 15. so if i
have not fudged the implementation, each character in the plain text would
have to be tested with 240 characters. and the only way to know if you have
a correct output is by looking at the resulting product. but of course, with
no referrance to what the original file is, an attacker can only guess as to
whether the cycle was successful or not. I also fixed it so that the likely
hood of using the same character out of one of the keys in the same place in
another key is almost 0. by this i have avoided for the most part a
reversal in the process. for any given block using any given key. by doing
this i avoid repetition, example, 'n xor m = x' 'x xor m = n' resulting in
no encoding taking place at all. the algorithm is available (not the
implementation) upon request so that it can be analysed somewhat. given that
the algorithm may be strong, but if it is implemented poorly that strength
is lost.
key:
say for example you have a 127 character string you want to encode, first
the string is padded so that the length of the key can be divided equally
into the string. second of all (using method 2 for the example) the user
defines part of the key, i'll say the first 8 bytes for the example. the
algorithm then uses a prng to concatonate 56 more characters ranging from
chr(16) to chr(255) to the initial 8 characters as defined by the user,
creating a 64 character key. this is placed in an array. then the algorithm
uses an offset to jumble up that key, i.e. the first character in the
original key becomes the last character in key 2, key 2 is concatenated to
key 1 and so on and so fourth until an additional 8 keys have been
concatenated to the original. this creates a key of 64 characters which is
then used to cycle through the text to produce the cypher. the padding is
then removed, in essence, characters in the key have been cut out of
sequence.
speed:
the implentations i have in code are tested on a AMD fx53 based system with
1gb ddr ram. cpu usage is at 100% while ram usage hovers between 40% and
50%. the second implentation can encode 13 files consisting of 9 jpegs of
around 30kb each, 1 executable of around 16kb and 3 source files of between
1kb and 2 kb in roughly 15 seconds. the first implementation is marginally
slower.
.
- References:
- Question about bit strength
- From: Antony Clements
- Re: Question about bit strength
- From: giorgio.tani
- Question about bit strength
- Prev by Date: Re: Death
- Next by Date: Re: Question about bit strength
- Previous by thread: Re: Question about bit strength
- Next by thread: Re: Question about bit strength
- Index(es):
Relevant Pages
|
