A Last Word on Ciphertext Expansion Ratio - Promise.

[Austin Obyrne <austin.obyrne@hotmail.com>]

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.