A Last Word on Ciphertext Expansion Ratio - Promise.

A Last Word on Ciphertext Expansion Ratio - Promise.

[Austin Obyrne]

Hi All,

Apologies first of all for what might seem another cross-group intrusion but there is something here that may be of interest to comp.lang.ada readers.  My interest is in cryptography which I don't admire a lot via Ada but I am committed to some ciphers I am promoting for various reasons that I was pitched into some years back.

I am grateful to a particular reader recently for the following recommendations in earlier posts that relate to his tests in 2013 on one of my vector ciphers.  I can say with some considerable satisfaction that his recommendations have now been implemented and the ciphertext expansion ratio is now down to an acceptable 11 to 1 (the industry standards have said 10 to 1 was acceptable in the past - don't ask me to defend that).  I could better this achievement but won't be doing so for reasons of my own.


Quote from his Simon's post:

" From the practical point of view, I think that the size of the encrypted 
files will be a serious issue. With the current code, they come out 
*more* *than* *30* *times* the size of the original, so that the 
encrypted SureCrypt85610.zip comes out at about 870 megabytes. Even if 
you output the encrypted data in binary the multiplier will be 12 (each 
byte of the original is encrypted as 3 integers). "

Unquote.

I have never felt there was anything for me to defend really in such a large ciphertext expansion given the relative cheapness of computer memory and computer power today (transmission and storage costs being the only issue) but I would like to explain some design principles that I was observing at the time while going overboard with such large ciphertext during the development of my cipher(s).  This is not an excuse! but an insight into a particular mindset.

Development of the cipher algorithm.

* At the time of designing my algorithm I envisaged  two main attacks on my cipher that I must counter i.e. 1) a cipher 'direct' attack in which an enemy cryptanalyst tries to break the ciphertext by inverting the cipher algorithm - i.e. by any means whatever but principally by using mathematical methods and 2) *the more insidious stealth attack on the frequency of the ciphertext string  - (note well,  no matter how powerful the cipher algorithm is it is still very vulnerable to this second 'implicit' attack and provision must be made to preempt this secondary attack by making sure there is no accidental giveaway information present).  That attack is based on  a statistical mapping correlation that might accidentally exist between the frequency of the ciphertext elements and the natural frequency of the language being encrypted (English in this case but the same applies to other languages).  The cryptanalyst looks for similarities and correlations that may exist between the ciphertext and the standard frequency table of the language of the plaintext - this is often the basis of so-called 'brute force' attempts to invert ciphertext by backdoor methods.

This form of attack is something I privately call a Kasiski- Babbage attack after the joint claimants to having invented it round 1856.  The Russian 'Kasiski' invented it firstly and the Englishman Charles Babbage claimed to have also invented it some 10 years later.

Note : that attack did not include the modern computer space bar which blows the lid on any character correlations that might be claimed today - the letter 'e' was the most frequently used character then but not today - (it has been overtaken by the space bar in my observations).  The attack method is still dangerous however.

The method I adopted to beat this attack was to make the ciphertext as far as possible  totally non-repeating (100% if possible but 70 % isochronous is ok) - this would ensure that the cryptanalyst who sought to do statistical mapping of the ciphertext to the plaintext it represented would have nothing to work with in terms of usable statistical 'samples'. 

That however means that in a message-length of say 10000 characters which isn't a lot really the ciphertext items would have each have to have 5 digits at least so as to accommodate all items .   There was no escaping the fact also that my vectors would have to have 3 columns of integer coefficients so the reader will see how it quickly it stacked up to such sizable ciphertext.  Coupled with this also is the fact that there was a nervous desire for extra 'entanglement' on my part that suggested a few more digits would not be out of order (this nervousness is an essential part of cipher designing - it is recommended (nay - essential) to anybody who is designing or testing out a cipher design).

The upshot of all of this is that there was some considerable 'overkill' in the eventual ciphertext of my first cipher which I have now put right. A variant of this cipher is now up and running although the original cipher is still being promoted as a perfectly good and useful cipher despite whatever people may say about it.

Comment

Given that security of information is on everybody's radar today and given also the relative cheapness of memory and computer power as the only variables that are being studied here then a large ciphertext expansion ratio while not to be encouraged is a small price to pay for the "Theoretically Unbreakable" communications it provides in return.  I have corrected that situation with better ciphertext expansion in any case now but the general philosophy is still valid.

A few more submarine cables and a few more communications satellites would do the trick if the data transmission super highway ever gets too crowded.  Having worked on submarine cable repairs in the North Atlantic for a few years I know the cost of implementing this claim and albeit expensive to lay cables on the oceanbed 2 miles down it is not enough to break the bank by any means I can assure you.

Once again I thank the group for their all-round help in this matter.

Demo.

Appendix. - The palindrome "able was I ere I saw elba" is encrypted here with this new ciphertext as a demonstration just to show the difference.

New.

322   693  -583  484  883  -817  444  719  -593  87 149  -14  -448 -902  1044  356 686  -648        373   645  -532  467  912  -831  -401 -966 1091  -231 -520  670 -440 -925 1052  87  166        -14    301   612  -535 114   122   13 -446 -963 1046  -291 -549  610 -443 -927 1049  439        934  -859  356  636 -549  391  725  -613  -441 -939  1051  67 121  -34 415  697 -622        502    921  -799  354  612 -551

The old ciphertext before this update for the same palindrome is shown below.

Old

8213296    5613955    7810389    9303946    8699396    7612477    5518730    5614599    4310443    7948109    6712411    9814278    5379275    3420529    6719119    4170894    6701860    5411938    9612643    4508877    6711548   10203033    7797301    8909868    9232898    5642932    7817078    9395167    6736856    4517866    2268846    5650033    6716145    9345149    5613350    5614276    8772813    5602736    6514061    9641302    6713240    9814509    9134444    4546023    6516139    8217907    5620732    7814906    1877689    3434031    7815545    2203005    5607389    6711572    8318502    4502636    5614047    5905334    5613064    3413213    8519042    3437998    5616641    4741355    5613276    4514596    4117763    6688395    5612590    3103864    7789902    3412395    9552022    7797481    5613441

Comment.

*Nothing on earth can invert and cryptanalyse  either one of these ciphertext strings. Rest assured I will not be giving away any side doors to the NSA ever. The two strings of ciphertext shown here are the upper and lower bounds of 5 possible intermediate encryption strings  of the same ciphertext - take your pick if you want to manipulate more ciphertext expansion - it is there for the asking.

adacrypt.

Re: A Last Word on Ciphertext Expansion Ratio - Promise.

[Dennis Lee Bieber]

On Sat, 6 Dec 2014 07:45:59 -0800 (PST), Austin Obyrne
<austin.obyrne@hotmail.com> declaimed the following:


>
>Appendix. - The palindrome "able was I ere I saw elba" is encrypted here with this new ciphertext as a demonstration just to show the difference.
>
>New.
>
>322   693  -583  484  883  -817  444  719  -593  87 149  -14  -448 -902  1044  356 686  -648        373   645  -532  467  912  -831  -401 -966 1091  -231 -520  670 -440 -925 1052  87  166        -14    301   612  -535 114   122   13 -446 -963 1046  -291 -549  610 -443 -927 1049  439        934  -859  356  636 -549  391  725  -613  -441 -939  1051  67 121  -34 415  697 -622        502    921  -799  354  612 -551
>

	Danger, Will Robinson, Danger

	The above indicates signed integer output... But that could be 16, 32,
or 64 bit integers internally.

	99.9% of the recognized encryption routines would take your 25-byte
(presuming ASCII) input and give back a 25-byte output. If the output is
then rendered for human reading it may expand to 50 bytes of hex digits, or
75 bytes if the hex bytes are space separated. Nowhere would it expand to
over 200 bytes.

>>> from Crypto.Cipher import DES3
>>> from Crypto import Random
>>> from Crypto.Util import Counter
>>> key = "SubKey01SubKey02SubKey03"
>>> len(key)
24
>>> len(key) * 8
192
>>> nonce = Random.new().read(DES3.block_size/2)
>>> nonce
'\xe2\xf7\\u'
>>> len(nonce)
4
>>> ctr = Counter.new(DES3.block_size*8/2, prefix=nonce)
>>> cipher = DES3.new(key, DES3.MODE_CTR, counter=ctr)
>>> plaintext = "Able was I ere I saw Elba"
>>> msg = nonce + cipher.encrypt(plaintext)
>>> len(msg)
29
>>> len(plaintext)
25
>>> len(plaintext) + len(nonce)
29
>>> msg
'\xe2\xf7\\u\xd3\xa3y\xe2\xd4\xdeqL\xfbJ\x02u\xbf\x9fQ%\xc6\x1f\x07\x82\x1a\xbd\x9c\x04\xad'
>>> " ".join("%2.2X" % ord(c) for c in msg)
'E2 F7 5C 75 D3 A3 79 E2 D4 DE 71 4C FB 4A 02 75 BF 9F 51 25 C6 1F 07 82 1A
BD 9C 04 AD'
>>> len(" ".join("%2.2X" % ord(c) for c in msg))
86
>>> " ".join("%d" % ord(c) for c in msg)
'226 247 92 117 211 163 121 226 212 222 113 76 251 74 2 117 191 159 81 37
198 31 7 130 26 189 156 4 173'
>>> print msg
?u?y?qL???Q%O\a??\x04

	The only reason the encrypted message is longer than the plaintext is
because it has been salted with a 4-byte random value, and that value is
provided so the decryption can set itself up for the same "randomness". The
reason for such a salting is so that two users, say, using the same key,
and the same plain text, would get different encrypted forms. You can't
look at the result and say "I know what user A sent... What user B sent is
identical, therefore I know what B sent" without even trying to decrypt the
message.
-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
    wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

Re: A Last Word on Ciphertext Expansion Ratio - Promise.

[mrvmurray]

On Saturday, 6 December 2014 15:46:00 UTC, Austin Obyrne  wrote:
> I have never felt there was anything for me to defend really in such a large
> ciphertext expansion given the relative cheapness of computer memory and
> computer power today ...

Whatever. If you won't listen, nobody will listen to you. A 10x increase in size is
BAD. Folks get uppity over a 10% increase!

> * At the time of designing my algorithm I envisaged  two main attacks on
> my cipher that I must counter i.e. ...

No attacker is going to conveniently stick to the only attacks you have
demonstrated you understand. They usually use the ones you demonstrate
an inability to counter, and if you don't even understand the attack, the
attacker has beaten you solidly.

> The upshot of all of this is that there was some considerable 'overkill' in
> the eventual ciphertext of my first cipher which I have now put right.

Nope. The attack which you are ignoring still stands. Brute force. That fact
that you don't understand how it could possibly work is my win.

> A few more submarine cables and a few more communications satellites
> would do the trick if the data transmission super highway ever gets too
> crowded.  Having worked on submarine cable repairs in the North Atlantic
> for a few years I know the cost of implementing this claim and albeit
> expensive to lay cables on the oceanbed 2 miles down it is not enough
> to break the bank by any means I can assure you.

Bullshit. Nobody is going to put in 10 undersea cables where one will do.
They won't even put 2 if 1 will do.

> Once again I thank the group for their all-round help in this matter.

The help you continue to reject, you mean?

Show your gratitude by taking the advice seriously, not dismissing it.

M
-- 

Re: A Last Word on Ciphertext Expansion Ratio - Promise.

[Austin Obyrne]

On Saturday, December 6, 2014 5:46:26 PM UTC, Dennis Lee Bieber wrote:
> On Sat, 6 Dec 2014 07:45:59 -0800 (PST), Austin Obyrne
> <austin.obyrne@hotmail.com> declaimed the following:
> 
> 
> >
> >Appendix. - The palindrome "able was I ere I saw elba" is encrypted here with this new ciphertext as a demonstration just to show the difference.
> >
> >New.
> >
> >322   693  -583  484  883  -817  444  719  -593  87 149  -14  -448 -902  1044  356 686  -648        373   645  -532  467  912  -831  -401 -966 1091  -231 -520  670 -440 -925 1052  87  166        -14    301   612  -535 114   122   13 -446 -963 1046  -291 -549  610 -443 -927 1049  439        934  -859  356  636 -549  391  725  -613  -441 -939  1051  67 121  -34 415  697 -622        502    921  -799  354  612 -551
> >
> 
> 	Danger, Will Robinson, Danger
> 
> 	The above indicates signed integer output... But that could be 16, 32,
> or 64 bit integers internally.
> 
> 	99.9% of the recognized encryption routines would take your 25-byte
> (presuming ASCII) input and give back a 25-byte output. If the output is
> then rendered for human reading it may expand to 50 bytes of hex digits, or
> 75 bytes if the hex bytes are space separated. Nowhere would it expand to
> over 200 bytes.
> 
> >>> from Crypto.Cipher import DES3
> >>> from Crypto import Random
> >>> from Crypto.Util import Counter
> >>> key = "SubKey01SubKey02SubKey03"
> >>> len(key)
> 24
> >>> len(key) * 8
> 192
> >>> nonce = Random.new().read(DES3.block_size/2)
> >>> nonce
> '\xe2\xf7\\u'
> >>> len(nonce)
> 4
> >>> ctr = Counter.new(DES3.block_size*8/2, prefix=nonce)
> >>> cipher = DES3.new(key, DES3.MODE_CTR, counter=ctr)
> >>> plaintext = "Able was I ere I saw Elba"
> >>> msg = nonce + cipher.encrypt(plaintext)
> >>> len(msg)
> 29
> >>> len(plaintext)
> 25
> >>> len(plaintext) + len(nonce)
> 29
> >>> msg
> '\xe2\xf7\\u\xd3\xa3y\xe2\xd4\xdeqL\xfbJ\x02u\xbf\x9fQ%\xc6\x1f\x07\x82\x1a\xbd\x9c\x04\xad'
> >>> " ".join("%2.2X" % ord(c) for c in msg)
> 'E2 F7 5C 75 D3 A3 79 E2 D4 DE 71 4C FB 4A 02 75 BF 9F 51 25 C6 1F 07 82 1A
> BD 9C 04 AD'
> >>> len(" ".join("%2.2X" % ord(c) for c in msg))
> 86
> >>> " ".join("%d" % ord(c) for c in msg)
> '226 247 92 117 211 163 121 226 212 222 113 76 251 74 2 117 191 159 81 37
> 198 31 7 130 26 189 156 4 173'
> >>> print msg
> ?u?y?qL???Q%O\a??\x04
> 
> 	The only reason the encrypted message is longer than the plaintext is
> because it has been salted with a 4-byte random value, and that value is
> provided so the decryption can set itself up for the same "randomness". The
> reason for such a salting is so that two users, say, using the same key,
> and the same plain text, would get different encrypted forms. You can't
> look at the result and say "I know what user A sent... What user B sent is
> identical, therefore I know what B sent" without even trying to decrypt the
> message.
> -- 
> 	Wulfraed                 Dennis Lee Bieber         AF6VN
>     wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

Hi Dennis,

Thanks for the tip.  Will be making changes chop chop - no advantage in having negative ciphertext anyway.

Austin.