Backdoor Found in Codecov Bash Uploader

Developers have discovered a backdoor in the Codecov bash uploader. It’s been there for four months. We don’t know who put it there.

Codecov said the breach allowed the attackers to export information stored in its users’ continuous integration (CI) environments. This information was then sent to a third-party server outside of Codecov’s infrastructure,” the company warned.

Codecov’s Bash Uploader is also used in several uploaders—Codecov-actions uploader for Github, the Codecov CircleCl Orb, and the Codecov Bitrise Step—and the company says these uploaders were also impacted by the breach.

According to Codecov, the altered version of the Bash Uploader script could potentially affect:

  • Any credentials, tokens, or keys that our customers were passing through their CI runner that would be accessible when the Bash Uploader script was executed.
  • Any services, datastores, and application code that could be accessed with these credentials, tokens, or keys.
  • The git remote information (URL of the origin repository) of repositories using the Bash Uploaders to upload coverage to Codecov in CI.

Add this to the long list of recent supply-chain attacks.

Tags: , , ,

Posted on April 21, 2021 at 11:12 AM • 45 Comments

Comments

metaschima • April 21, 2021 4:43 PM

This is extremely shameful. Bash is not like C, it is a lot more difficult to create obscure code that has a nefarious purpose. The fact that a line was added that calls curl and nobody inspected it more closely before approving it is just appalling. Shame on the devs for missing this.

Ismar • April 21, 2021 4:43 PM

Ok,
One more of these articles where not enough attention is given to the root cause of the issue-namely how the code base was compromised in the first place. In other words, what allowed the attackers to place the curl line in the code base, and stop usage of the code repositories of this type until the problem is fixed.
given that the checksum itself was not compromised should be a big clue in the investigation.

Anders • April 21, 2021 4:52 PM

@Ismar

Root cause : “In this attack, threat actors had gained Codecov’s credentials from their flawed Docker image”

hxxps://www.bleepingcomputer.com/news/security/hundreds-of-networks-reportedly-hacked-in-codecov-supply-chain-attack/

Ismar • April 21, 2021 8:16 PM

@Anders- Thanks,
I was reading the other arstechnica article, but still even with this article the cause is jut mentioned in passing with developers blamed for not checking the checksums more often- I am a developer and can tell you people don’t have time to perform these checks all the time. So maybe this checksum check should be included (automated) as part of the standard dev repository workflow

SpaceLifeForm • April 21, 2021 9:25 PM

@ Ismar, Anders

My hunch is that the problem was originally discovered because someone noticed the unexpected outbound traffic. Then started looking deeper. Searched for ip address in their development tree, found the script. Then proved it via the hash.

You can get an idea of how many different projects have been impacted here

https://grep.app/search?q=https%3A//codecov.io/bash

David Rudling • April 22, 2021 2:43 AM

Related. An unusual source has been identified for some vulnerabilities in the Linux kernel

ht tps://www.osnews.com/story/133327/university-banned-from-contributing-to-linux-kernel-after-intentionally-submitting-vulnerable-code/

Denton Scratch • April 22, 2021 9:27 AM

This impresses me not very much:

bash <(curl -s https://codecov.io/bash)

That seems to be Codecov’s recommended way of running the bash uploader: executing some piece of bash script from over the internet, on your machine, without first inspecting it.

https://docs.codecov.io/docs/about-the-codecov-bash-uploader

There is mention made of a hash on that page; but it’s way down below the fold, way below the bash command.

I went there to find out what Codecov and their bash uploader are meant to do; the moment I saw that, I stopped reading and ran away. This doesn’t seem to be an outfit that cares much about security. Why are people still doing this?

I have no idea what benefit I’m supposed to gain by uploading information from my machine to this company. It says that what it does is:

detect the environment
gather reports
upload them to Codecov

That’s awfully hand-wavy. What’s in these reports? Apparently it searches the filesystem for code-coverage reports from CI systems, and sends them to Codecov. Are these uploads encrypted on the wire? How can I be sure they are not also uploading SSH keys, correspondence with my lawyer about my divorce settlement, or my Contacts file? Well, that’s easy – download the bash script and inspect it. But then why are they encouraging me to execute it without inspecting it?

epic-irc'r • April 22, 2021 12:04 PM

metaschima: yes, shame on the devs for permitting it, but also, people need to become more open-minded just to the very possibility that their bash code might have bugs. I’ve seen a bug report on bash code turn in to a verbal turf war knife fight over nothing more than ego, based on the idea that bash is easy so anyone can do it, so anyone’s shell code is just as good as anyone else’s, and that’s ignorance plain and simple. It is ridiculous, and it must be mocked, mercilessly and with crumpets.

1&1~=Umm • April 22, 2021 12:35 PM

@ epic-irc’r

it must be mocked, mercilessly and with crumpets

Hmm or should I call you “Idle, Eric” and ask you about Python?

SpaceLifeForm • April 23, 2021 6:45 PM

@ Denton Scratch

The ‘hack’ was to upload the users shell environment variables.

There can be a lot of UI there (ex:DB creds), but if your ssh key is there, you should probably not be allowed near a computer.

Weather • April 24, 2021 1:19 AM

@slf
Real hackers have already pwned the device, the script kiddies take there anger out on 127.0.0.1 🙂

Weather • April 24, 2021 5:37 PM

@slf
I quickly whios aprnic and 127/8 it say there’s no registered domain ? Is it a Tla

YASCA • April 24, 2021 11:15 PM

Yet Another Supply Chain Attack

https://arstechnica.com/gadgets/2021/04/hackers-backdoor-corporate-password-manager-and-steal-customer-data/


As many as 29,000 users of the Passwordstate password manager downloaded a malicious update that extracted data from the app and sent it to an attacker-controlled server, the app maker told customers.

In an email, Passwordstate creator Click Studios told customers that bad actors compromised its upgrade mechanism and used it to install a malicious file on user computers. The file, named “moserware.secretsplitter.dll,” contained a legitimate copy of an app called SecretSplitter, along with malicious code named “Loader,”

1&1~=Umm • April 25, 2021 1:29 AM

@YASCA

It sounds so much more “SolarWinds OMGish” if you pull out a couple of different quotes 😉

“Passwordstate is trusted by more than 29,000 Customers and 370,000 Security and IT Professionals around the world, with an install base spanning from the largest of enterprises, including many Fortune 500 companies, to the smallest of IT shops.”

And,

“The breach is especially concerning because Passwordstate is sold primarily to corporate customers who use the manager to store passwords for firewalls, VPNs, and other enterprise applications.”

@ALL

Anyone taking a “book/pool” on how long before someone in the US Gov says “Russia” or one of the other three?

The reality is that the problem, that once used to be just a case of,

1, Limitations of the average human.

Now has further problems,

2, Users need to use multiple services concurrently.

3, The services people use are now based on the Internet / Cloud.

4, Nearly all users are now thanks to COVID and ISP policies not tied to an IP address or verifiable location.

Back in the early 1980’s the ‘Human limitations with passwords’ had got to the point that even then it was ‘a very serious concern’… So hear we are getting on for a ‘working life’ later or 25 IT-Generations later where our technology is supposadly 30million times more powerful, we’ve not solved the problem we’ve only made it worse with another human failing ‘convenience’.

So two human failings, -both of which are getting worse with time- have through one or two other human failings -stupidity arising from pride&greed- rendered what for atleast one Western Nation is ‘critical infrastructure’ of overwhelming National Security importance practically, not just theoretically insecure…

People need to understand that the life of the password should have been over by the mid 1990’s at the absolute latest. But it’s still here on full life support…

A password is in effect a ‘token’ and it has the same down sides every bit as bad as the ‘One Time Pad’, then a few more on top. Any cryptographer can tell you why the OTP though beguiling simple and with the promise of ‘Perfect Secrecy’ is in reality a very bad idea to use. Why they do not say the same about passwords is I guess more a question of ‘Why people do not ask them?’.

Oh and do not think most of the ideas about ‘two factor’ usage is going to help. 2FA systems are just as insecure but in different ways, again through the same human failings.

Weather • April 25, 2021 3:25 AM

@1&1~umm
Why is it abad idea to use Otp that password have the same flaw…no dangling carrots 😉

1&1~Umm • April 25, 2021 1:52 PM

@Weather:

“Why is it a bad idea to use Otp that password have the same flaw…no dangling carrots”

If you think about the big disadvantages of the OTP and likewise the ordinary password and make a list for each, when you compare them you will find that they have quite abit in common.

The difference though is whilst we avoid the disadvantages of the OTP, we just ignore the same disadvantages in the password…

It takes only a moment to realise that historically a password is a secret that should only be used once.

That is passwords when sent between a user and a computer are only as secure as the link in between. If as used to be the case with serial terminals, there was,

  1. No information security
  2. No electrical/elrctronic security
  3. Effectively no physical security

In essence the link was little different to a ‘broadcast’.

So for a while the link security was purely physical with metal conduits, significant walls, and in some cases armed guards. However for various reasons both resource and security they were insufficient as all purely physical systems are. The only security they provide is ‘time delay’ and then only if someone ‘walks the line’ every little while.

Slightly later anti tamper alarms were added. But be they mechanical, electrical or electronic they were like purely physical security all they replaced was some of the ‘walking the line’. They were still very much dependent on the time delays of the physical systems to alow for other response systems to be initiated. Also none of them were realy secure, due to the principle of ‘what man can make man can fake’. That is if an alarm can be installed it can be in some way defeated silently by an attacker so no alarm is raised.

Whilst this is less of an issue with physical objects, information objects like passwords cost next to nothing to copy, and are them just as usefull as the original.

Thus the security needed to move from a reactive model of alarms, time delay and response, to a proactive model. So eventually ‘information system protection’ was implemented. Usually in the form of some kind of link encryption. However before the late 1980’s encryption and the attendent issues was either eye wateringly expensive or increadibly slow. Also realistically not all that secure for various reasons. So it took the time delay out from minutes/hours of physical/electric security out to weeks/months of ‘commercial level systems’ to months/years for ‘state level systems’. Hence the reason for changing passwords every week or month, which we still slavishly follow these days though few understand why.

The problem with naff old crypto is that one attack that would be very difficult these days was very much simpler back when “link crypto” was mainly simple streams based crypro and thus subjecy to an “attack in depth”. Due to the way things work, almost exactly the same way for logging in knowing what and when the plaintext is would enable a low grade stream cipher to be broken relatively quickly, thus the password recovered.

There are other asspects to consider but this post is long enough.

If you assume not unreasonably that link encryption is always going to be vulnerable eventually without several other changes being made. Then consider a true one time password, it can not be guessed and the only way to attack the system is in effect grab the link in a form of MITM attack such that the attacker gets the access from the user and hijacks the session in some way.

There are ways such session hijacking can be prevented these days but they are generally not used.

The other problem as RSA token users found. Most supposed One Time Passwords are not random, but made by a crypto algorithm. If the “seed” is aquired then it’s game over as anyone can then reproduce the passwords. To help prevent this there are certain “time sync” based protocols built in as well as login counters, however the more secure such systems are made the more fragile they become in the face of user errors, thus they appear unreliable.

So ‘security -v- convenience’ becomes a trade off with conveniance winning in most cases.

Things just get one heck of a lot more difficult when “Single Sign On” systems are used. Many issue “tokens” that get put in the users environment in some way. Due to the fact users might have three or four Web Based systems open at the same time from the same browser, the lack of issolation present in such sustems means that some applications would be able to get the tokens of other sessions due to poor internal seperation in the browser.

Likewise password managers with web interfaces are not a good idea.

The only real solutions are,

1, Replace password systems.
2, Some how remove human failings such as poor memory.

SpaceLifeForm • April 30, 2021 4:35 PM

@ ALL

Check your logs.

https://www.bleepingcomputer.com/news/security/codecov-starts-notifying-customers-affected-by-supply-chain-attack/amp/

Known IPs In Scope:

The originating IPs used to modify the bash script itself:

79.135.72.34

The destination IPs where the data was transmitted to, from the compromised Bash Uploader.
These IPs were used in the curl call on line 525 of the compromised script:

178.62.86.114,
104.248.94.23

Other IP addresses identified in Codecov’s investigation, likely related to the threat actor and associated accounts:

185.211.156.78
91.194.227.*

Other IPs that may be related to this incident (not confirmed by Codecov):

5.189.73.*
218.92.0.247
122.228.19.79
106.107.253.89
185.71.67.56
45.146.164.164
118.24.150.193
37.203.243.207
185.27.192.99

Wandee • June 1, 2021 4:28 AM

@ 1 & 1~=Umm

‘A password is in effect a ‘token’ and it has the same down sides every bit as bad as the ‘One Time Pad’, then a few more on top. Any cryptographer can tell you why the OTP though beguiling simple and with the promise of ‘Perfect Secrecy’ is in reality a very bad idea to use.’

What are the down sides of the One-Time Pad? Why is it a bad idea to use a OTP and who are the cryptographers telling us why? Maybe if we go back to Shannon’s papers and look at page 682 and what he had to say about the Vernam cipher, we might come to different conclusions.

A plaintext we know, it doesn’t hold entropy at all. It is the property that in its own right can be measured when attacking a cipher. Remove that property by turning it into a random string before encrypting it, will remove that property, giving perfect secrecy for a cipher. No key transmission required for each cipher created, only a one time exchange of a small secret between sender and recipient, which is reusable.

1&1~=Umm • June 1, 2021 7:11 AM

@Wandee

Firstly, your statment of,

“A plaintext we know, it doesn’t hold entropy at all”

Is very badly phrased and can be read to mean more than one thing… Such are the joys of the english language.

So formally a ‘known plaintext’ amongst the parties whilst it does not have any entropy, neither does it convey any information directly.

This can be seen with the customary openings salutations of ‘Hi’, ‘Hello’, ‘Hope this finds you well’, etc in a message, they may be polite but generally they carry no information.

However they do have a significant downside, in that if their use is “standard” as happens with organisational messages such as those the Military etc use. Then they do reveal “key stream” as a consequence of their use, so ‘known plaintext’ should always be avoided. Especially with ‘Stream Ciphers’, where the mixing function has no ‘diffusion’ and very minimal ‘confusion’.

Remember Microsoft Office Word files used to have something like 4kBytes of such ‘Known Plaintext’ at the begining of every file sent from the same PC (Something I’m sure the SigInt agencies were very happy with as were Law Enforcment Agencies).

But to get back to your question,

“What are the down sides of the One-Time Pad?”

It has a quite a number, but the primary one is that the security rests entirely on the ability of an attacker to determine the key stream material at any point in time.

The difference in use between the One Time Pad and a Stream Cipher is very small, and is to do, not with the actual mechanics of using the system, but the way the key material is,

1, Generated
2, Distributed
3, Stored
4, Used
5, Destroyed

The OTP proof of security is not that it some how hides the plaintext or it’s syatistics from being discovered, but that,

6, All messages are equiprobable

That is based on the ‘assumption’ that the only attack open to a third party should be a ‘brute force search’ which will produce as many plaintext candidates, as the key space used for the ciphertext message sent. So the third party should have no way of determining which plaintext is valid… which in reality is very difficult to achieve (few systems are ‘issolated’).

So taken on a bit by bit basis for a ciphertext message of N bits in length there are 2^N possible plaintext messages all of which ‘should be equally as probable’.

This has two consequences,

7, The number of messages for any bit length is finite.
8, The shorter the messages sent the less secure they are.

The obvious follow on consequences are that “key reuse” will happen, and also at some bit length the security is that equivalent of a simple substitution cipher, not even a polyalphabetic substitition cipher.

There is also another consequental issue that does not get much talked about which is,

9, Not all keys in a given key space are equally as secure.

That is there are ‘repeating subset’ and ‘run length’ issues. The most obvious is all bits being either set or clear so ‘000000…0’ is going to reveal any plaintext ‘11111…1’ reveals the plaintext inverse. But obviously a two bit pattern repeated over and over ‘010101…01’ or ‘101010…10’ is not much more secure either, and so on. There is also the fact that for any given key space half the keys are inverses of the other half and so on (look up Walsh Functions for the details on sequency space).

Which means that there is a lot more issues the just the usually quoted difference of the ‘key stream’ being,

“Generated by a ‘Truely Random’ physical process for the OTP and a ‘Complex determanistic’ logic process for a Stream Cipher.”

Oh what you describe with,

“No key transmission required for each cipher created, only a one time exchange of a small secret between sender and recipient, which is reusable.”

Sounds like you mean a “stream cipher” not a One Time Pad.

Wandee • June 3, 2021 7:04 AM

@ 1 & 1~=Umm

Firstly, thanks for pointing out the me that the phrasing of my sentence could have different meanings, so already a cipher in its own right. 🙂

I have read your comment several times, only to make sure I understand the points you trying to make. So let’s start from the end and work our way up to the top.

You wrote: “Which means that there is a lot more issues the just the usually quoted difference of the ‘key stream’ being, “Generated by a ‘Truely Random’ physical process for the OTP and a ‘Complex determanistic’ logic process for a Stream Cipher.” Oh (I assume you meant Or) what you describe with, “No key transmission required for each cipher created, only a one time exchange of a small secret between sender and recipient, which is reusable.” Sounds like you mean a “stream cipher” not a One Time Pad.

I still don’t understand the difference between “Truly random” and “Random”. Either the outcome of an event is random or it isn’t. The word truly only muddies the waters and doesn’t add anything, but only confuses. I checked Shannon’s papers but couldn’t find one instant where he mentioned “truly random”.

If we look at physics, mathematics or computer science than deterministic means no involvement of randomness and the future states of a process. A deterministic system will always produce the same output from an initial state.

Your definition of a stream cipher might be your personal view on it, but is not a universal view shared by others and you might look that up by googling it. The OTP is a stream cipher. Let’s see how Shannon looks at the Vernam cipher and how to turn it into a OTP:

“The situation is somewhat more complicated if the number of messages is infinite. Suppose, for example, that they are generated as infinite sequences of letters by a suitable Markoff process. It is clear that no finite key will give perfect secrecy. We suppose, then, that the key source generates key in the same manner, that is, as an infinite sequence of symbols.”

You find this at “A Mathematical Theory of Communication by C.E. Shannon – The Bell System Technical Journal, Vol. 27, p. 682, July, October, 1948. | Online Link: A Mathematical Theory of Communication

The short secret I’m referring to is not the key, but part of a Markov process. We use the secret to transform the plaintext into a random string, but also as suggested by Shannon to generate our key.

A Markov process is a random process whose future probabilities are determined by its most recent values. They are natural stochastic analogs of deterministic processes and form one of the most important classes of random processes.

Your example with a string of binaries isn’t very convincing since it is based on assumptions and the mathematics you produce fit the quote Nicola Tesla made nearly 100 years ago: Today’s scientists have substituted mathematics for experiments, and they wander off through equation after equation, and eventually build a structure which has no relation to reality.

Your first assumption is that the plaintext is a string of fixed binaries ‘0000….0′. Your second assumption is that the key is a repetitive string of two bits ’01’.

This quote fits your binary example and the conclusions you draw from it. Now think about it what happens if you have a transformation of the plaintext prior encryption. The secret for the transformation and encryption shared between sender and recipient could be 4 bits, but for an adversary each bit always carries a 1/2 probability. Introduce a modus that isn’t repetitive and your cipher has perfect secrecy. If you want to know how it’s done let me know and I give you a link to a website, which comes with the mathematical proof.

On the website is explained by using examples how it works with language alphabets, the hexadecimal system etc. Here a little binary example:

Binary addition: 0 + 0 = 0; 0 + 1 = 1; 1 + 0 = 1; 1 + 1 = (1)0 (which is 0 and carry 1 )

Let the shared secret be 0 1 0 1 and after transforming the plaintext turns into 0 1 1 0 used for encrypting the transformed plaintext.

Now take any plaintext and turn it into binary (length doesn’t matter); transform it using the secret; encrypt the transformed plaintext with the changed (secret) creating a cipher. The cipher is the only data an adversary can intercept and now put yourself into the position of an adversary and attack the cipher. (Tip: the secret of 4 bits = 2^4; 0000 to 1111).

Looking forward to the mathematics you come up with.

Weather • June 3, 2021 8:32 AM

@wanndee
No offensive, but you didn’t say much in that post, your early one, yes if the plaintext is encrypted then a Otp will be harder to attack, but using it twice, the secondary encryption will still break the Otp , its a extra step but a small one.

JonKnowsNothing • June 3, 2021 10:34 AM

@Wandee

re: the difference between “Truly random” and “Random”. Either the outcome of an event is random or it isn’t.

It depends on how the “random” is created. Computer generated random numbers are often Pseudorandom although they are used in many applications. Truly random numbers are not hard to generate but most often are not used because not everyone wants to carry a bag of 20D dice to create them.

===

ht tps://en.wikipedia.org/wiki/Pseudorandomness

Pseudorandomness measures the extent to which a sequence of numbers, though produced by a completely deterministic and repeatable process, appear to be patternless.

The pattern’s seeming randomness is the crux of much online and other security. Since the sequence is repeatable, it is important that the seed which, together with a generator produce the numbers, be well chosen and kept hidden.

ht tps://en.wikipedia.org/wiki/Diceware

  • Diceware is a method for creating passphrases, passwords, and other cryptographic variables using ordinary dice as a hardware random number generator.

ht tps://en.wikipedia.org/wiki/Dice#Polyhedral_dice

  • Various shapes like two-sided or four-sided dice are documented in archaeological findings e.g. from Ancient Egypt or the Middle East. While the cubical six-sided die became the most common type in many parts of the world, other shapes were always known, like 20-sided dice in Ptolemaic and Roman times.

(url fractured to prevent autorun)

1&1~=Umm • June 3, 2021 11:38 AM

@Wandee:

“I still don’t understand the difference between “Truly random” and “Random”.

I’m not surprised you say that, because you go onto say,

“Either the outcome of an event is random or it isn’t.”

That statment is not true of random sequences because ‘random’ is at best ill defined, and has a spectrum of meanings that also depend on who is making the claim at the time. Also ‘events’ are singular and have probabilities, they are not ‘sequences’ which have distributions.

Hence the Internet joke of,

“4 is a random number”

(it’s actually a random drawing from an Urn with an unknown number of balls in it that when graphed out in their entirety have a distribution which can not be determined from a single ball).

A simple thought experiment for you,

Two people decide to run an experiment where the second party examines the output of what to them are two black boxes that have been created by the first party.

The object of the experiment is for the second party,

‘To observe the outputs of the two black boxes for a finite time and make a pronouncment of if the boxes contain a random generator or a determanistic generator.’

Their findings will be one of the following,

1, Neither is random.
2, The first is not, the second is.
3, The first is, the second is not.
4, Both are random.

The first party has a choice of putting in each box either,

A, A ‘True’ Random Generator (TRNG)
B, A ‘psuedo’ Random Generator (PRNG) using a determanistic generator and a determanistic masking process that is an analog of (ie mimics imperfectly) a TRNG output.

What should be clear is that whilst the first party can authoritively say ‘true’ or ‘psuedo’ for each box as they built the generators, the observing second party can not. That is the second party can only make a probabilistic choice to say how random they think the ouputs are, based on the finite samples they have.

In the ‘Handbook of Applied Cryptography’ by Alfred J. Menezes et al §5.2 Random bit Generation they say,

“A (true) random bit generator requires a naturally occuring source of randomness. Designing a hardware device or software program to exploit this randomness and produce a bit sequence that is free of biases and correlations is a difficult task.”

In §5.3 Pseudorandom bit generation they say,

“A one-way function f (Definition 2.12) can be utilized to generate pseudorandom bit sequences by first selecting a random seed s, and then applying the function to the sequence of values s, s+1, s+2,…; the output sequence is f(s), f(s+1), f(s+2),….”

If we now examine the statment you give of,

“A Markov process is a random process whose future probabilities are determined by its most recent values.”

You will see it matches the §5.3 description of a pseudorandom bit generator, not that of a ‘true’ bit generator given in section §5.2.

You may be being confused by the use of ‘natural’ in the rest of the statment,

“They are natural stochastic analogs of deterministic processes and form one of the most important classes of random processes.”

It implies ‘a good facsimile to’ not ‘a physical process’ that is only constrained by the laws of nature. Thus it in no way precludes it being entirely determanistic, which it is.

The reality is in general Markov processes are almost as woolly defined as random is… Which is a bit of a problem. About the only thing agreed on is,

1, A Markov process is a stochastic process that satisfies the Markov property characterized as “memorylessness”.

2, Where “memorylessness” means the output is conditional ONLY on the present state of the system.

That is whilst it’s future and past states are independent, it in noway means that they are not “determanistic”.

The simple function ‘n+1’ in a field used in a binary counter lacks only the ‘Stochastic’ requirment. Which can be provided by a lookup table, where the members indexed of the set have some probability curve, be it a flat, normal, Poisson, etc distribution. Such a lookup table can be devolved into two or more sequential used lookup tables, the first being a table generated by the use of a random oracle to give a random but fully determanistic uniform probability (flat distribution). The second and subsequent lookup tables map the probability curve as you would graph it. Combined you get a ‘random field’ in as many dimensions as is required (to form the required manifold).

Obviously the lookup tables can be replaced with functions that give as much precision as you wish. The table generated by the random Oracle can be replaced by one or more block ciphers and keys.

You might want also want to look up what a ‘Chaotic Process’ is,

https://en.m.wikipedia.org/wiki/Chaos_Theory

The lesson to learn is,

“What you as an observer consider to be random by statistical or other measurement can be fully determanistic thus fully predictable”

Which means that it falls under Kerckhoffs’s principles, which was reformulated by Claude Shannon as “the enemy knows the system”.

So it can not be used for a One Time Pad, as it destroys the fundemental principle that gives the OTP it’s ‘Perfect Secrecy’ that “the enemy can not know the system”. So renders it no more than a fully determanistic stream cipher.

You should read Menzies et al, and Chapter three in Vol 2 of Donald Knuth’s The Art of Computer Programing a careful study of those will give you answers to the issues you are having.

MarkH • June 3, 2021 3:23 PM

@Wandee,

Intending no personal disrespect, I guarantee that the conception you have presented is comprehensively mistaken. No shame in that; I estimate that many thousands of students of cryptography have gone down the same dead-end path.

Here’s a succinct treatment from Wikipedia with a most instructive title:

Stream Cipher: Loose inspiration from the one-time pad

I especially commend your attention to these words (my emphasis added):

A stream cipher makes use of a much smaller and more convenient key such as 128 bits … However, this comes at a cost. The keystream is now pseudorandom and so is not truly random. The proof of security associated with the one-time pad no longer holds.

I suggest that one fundamental error in the reasoning you offered is based on a misunderstanding of Markov processes. You wrote, “The short secret I’m referring to is not the key, but part of a Markov process.”

A Markov process is defined — usually compactly — in terms of a set of parameters, but each transition from a state to its successor is, by definition, chosen at random according to a specified distribution.

If a Markov process is rerun multiple times from a given initial state, the successor states will show multiple trajectories. If the trajectory is repeatable (as would be required for decryption), then it is not a Markov process. If that “short secret” determines the succeeding states then no, it is NOT a Markov process.

Consider the quote you offered from Shannon.

[Note: the Shannon citation you posted is incorrect; it should be:

Shannon, Claude. “Communication Theory of Secrecy Systems”, Bell System Technical Journal, vol. 28(4), page 656–715, 1949]

Let’s look at the next three sentences following the ones you quoted:

Suppose further than only a certain length of key LK is needed to encipher and decipher a length LM of message. Let the logarithm of the number of letters in the message alphabet be RM and that for the key alphabet be RK. Then, from the finite case, it is evident that perfect secrecy requires

RM LM ≤ RK LK .

Shannon’s conclusion here is precisely equivalent to “perfect secrecy requires the number of key bits be not less than the number of message bits.”

Note well that key does not mean keystream. If by 128 bits I can represent any process — “Markov” or not — that will generate a 12 petabyte keystream, the key is not 12 petabytes long. It’s 128 bits long.

The concept of randomness (as used technically) is abstract, baffling and unintuitive.

Here’s a perhaps helpful way to think about it. If done properly, coin tosses or die rolls can have very nearly equal outcome probabilities, and be unpredictable. Their outcomes are not determined by previous outcomes.

Imagine that someone tosses a “fair coin” 10,000 times. Analysis of a record of outcomes will usually show that the counts of “heads” and “tails” are both quite close to 5,000. What such analysis can not do, is help you predict the outcome of the ten thousand and first toss: it’s 50/50, and nobody can predict which.

Equivalently, suppose that you apply some chosen lossless data compression algorithm to the record of 10,000 coin tosses expressed as a bit sequence. Almost every time, the bit sequence cannot be compressed, or will compress by only a very few bits. With extremely low probability, there may be highly patterned sequences (like “it’s all tails!” or “it’s ASCII for Lincoln’s Gettysburg address!”), but in almost all cases the sequence is practically uncompressible.

A stream cipher keystream will show the same properties for any standard compression algorithm, but the keystream generator is an algorithm which predicts the entire keystream from a few bits of actual key, effectively compressing the long keystream to a short key. In other words:

For a long keystream generated from a short key, there exists at least one algorithm (the keystream generator) which always enables1 very high compression. The very existence of the generation algorithm can be thought of as a sort of trapdoor.

With a truly random keystream — the kind required by Shannon — no such algorithm does or can exist. There is no trapdoor.

I hope that the discussion here will enlarge your understanding!

  1. If the key is long and the cipher is strong, then finding the key (i.e., cryptanalysis) may be impractical, but can be done in principle, if only by exhaustive search. For the actual Vernam cipher — with truly random keystream material — no such reduction is possible, even with infinite resources. ↩

Weather • June 3, 2021 3:43 PM

Just updating what I said, if a plain text is encrypted and then put through a Otp , working in reverse the Otp might equal 1 or 2 which is the siq of the encryption function, if you use the Otp key again the output siq will equal 1 or 2 but the same as the first code, in this example you’re cut the key length by 50%

Weather • June 3, 2021 6:00 PM

@wandee
Most ciphers use binary maths, or,and,xor,shift,roll which is capped at byte, like what others have said should be 256 byte length, is 256 unqine chars not 32 out of 256, basic maths function like +,-,/,* can access up to 32-64 bit bytes but then you run into the problem of parreellel maths, say you do a for loop from 0-256 added, it will equal 0x7f80 ,if you have some complex function, you can input that, at the end filter say 0x7f41 that in one instruction give a output that would be if you started with that, now for course, try to break rc5 or prime numbers down to basic maths, in realtime you could decode it. Hint similar try to create a 4 digit pin that will select a substitute box for aes 10000 that changes ever 15 mins and needs input from user, plus padding like openssh does, plus workout the most process intevise CPU usage and set the min reply time to that.

Wandee • June 3, 2021 9:23 PM

@ 1 & 1~=Umm

@ Weather

First of all thanks for taking an interest in my comments and @Weather no offense has been taken. Without criticism and sometimes even insults over the last 4 years I might have given up.

Still my question for the mathematical solution to the problem I posted has not been answered. So let’s create a cipher and I trust you will have no problem to provide the math to crack it. I will leave the possible binary additions, because it might assist you.

Binary addition: 0 + 0 = 0; 0 + 1 = 1; 1 + 0 = 1; 1 + 1 = (1)0 (which is 0 and carry 1 )

Plaintext: ? ? ? ?

    Secret : ? ? ? ? +

Transformed plaintext: ? ? ? ?

    Modified Secret: ? ? ? ? +

Cipher: 1 0 0 1

Put yourselves into the boots of an adversary who has intercepted the cipher and let me know if the plaintext is 0000 or any of the possible combinations leading to 1111.

Again, thanks for taking an interest.

Wandee • June 3, 2021 11:28 PM

@Markh

Hi Mark,

No offense taken since criticism as strong as it might be are the spice ingredient of a fruitful argument. Still I am not a student of cryptology/cryptography and a nonbeliever in estimates, so couldn’t tell how many have gone the road I took. You call it a death-end path; I see it more as a road out of the mathematical jungle encryption has ended up in.

I wouldn’t regard Wikipedia as the final authority for a definition on stream ciphers, but only one of many sources (crypto.stockexchange.com for example is one), with different definitions what constitutes a stream cipher.

Thanks for pointing out the citation and you are right I got the wrong paper there, I copied the wrong citation from my website (quite a few citations from him there), referring to a different point I make.

I appreciate that you quote Shannon again and point out to me that key doesn’t mean keystream. However, if you have read Shannon you will have noticed too that his plaintext constitutes always a property that can be measured. Remove that property and turn it into a random string, the key is not the problem anymore.

Take an English text of 2000 characters and turn it into a random string of characters. The logarithm for language alphabet (RM) and key alphabet (RK) are identical with 26 characters. According to Shannon this is not perfect secrecy since the length of the message characters exceeds the length of the available unique keys. Let i = 1 to 2000, n = 0 to 25, m = message character and k = key character. The algorithm for the OTP now is as follows:

mi(n)+ ki(n) = ci | Mod26

These are 2000 individual equations and now tell me how from a cipher you find the path to the plaintext. Looking for frequency, pattern or character combinations? What property you going to measure? Is it possible to recreate the random string, without having access to the key, because the random string and the secret is required to turn it back into the plaintext.

Weather • June 4, 2021 12:55 AM

@wandee
Rc5 has a siq of lower chactors, aes has a even dispution of equal property, they both give a SIG,its the same as plaintext saying ‘thisisthepassword’ you have asked two question I need to think about.

Weather • June 4, 2021 1:03 AM

@wandee
I gave you a answer to that post, using unknown encryption and a One time pad, and no if you can flatter me your in the wrong game

MarkH • June 4, 2021 10:10 AM

@Wandee:

I don’t understand what you’re driving at.

I recommend looking at the Wikipedia pages for ciphers such as RC4 or El Gamal, as examples of how to make a comprehensible and unambiguous description of a cryptosystem.

If you want insightful criticism of your invention, the best way to seek that out is to write it up clearly and succinctly so that knowledgeable people can read it in 10 minutes (or much better, 5 minutes).

Then if you’re lucky, someone who understands cryptography will be patient and generous enough to explain why the invention doesn’t achieve what you seem to believe it does. The open mind can absorb much knowledge!

Every claim for a perpetual motion machine (whether “zero point energy” or anything else) from which useful work can be extracted, has been false.

Every claim for objects or signals moving faster than the speed of light in vacuum, has been false.

Every claim that a cryptosystem achieves Shannon’s perfect secrecy without the need to communicate a volume of key material at least as large as the message traffic, has been false.

When a young friend of mine was in his teens, sometimes he would tell me about a tech project he and his friends had cooked up, which I was confident couldn’t succeed. They were all very bright, and were simply wandering into territory they didn’t know much about.

Rather than pour cold water onto youthful enthusiasm, I would respond to the ideas by saying, “son, you’re going to learn a lot!”

Weather • June 4, 2021 3:56 PM

@markh
I know you view point on the matter, but you can compress a 700mb file down to 1000bytes and expand it, probilty comes into it, extreme compression your look at 60% possibly data success as 1 byte compression your look at 90% I posted the general just early but wrapping it up in a pagage yes won’t work, but wet wear is if it looks like a book it expanded correct or if PE runs with out crashing is correct.
If @mod doesn’t mind the spam I’ll post C code for compression and expansion, and give you a BMP picture compressed, but warning it will probably take a year to expand, its serial instruction, you can’t really parrellel it.

Bending the laws not breaking them, but I know you view on the matter.

MarkH • June 4, 2021 4:33 PM

@Weather,

Some of your English was indecipherable to me.

I didn’t mean to suggest that lossless data compression can’t be done … I use it all the time!

However, the average reduction for a truly random bit sequence is very nearly zero. This is always true for lossless compression algorithms, no matter how clever (or computation intensive).

1&1~=Umm • June 5, 2021 9:18 AM

@Wanadee:

“Your definition of a stream cipher might be your personal view on it, but is not a universal view shared by others and you might look that up by googling it. The OTP is a stream cipher.”

The basic definition of a stream cipher super set is that,

1, It has a simple mixing function of a limited alphabet / width.
2, The mixing function has two inputs one for a character A of message M the other for a key K.
3, The key K, remains the same for encryption and decryption.
4, The message M is plaintext P for encryption, and ciphertext C for decryption.
5, The mixing function output is ciphertext C for encryption and plaintext P for decryption.
6, The mixing function f is reversable thus C=f(P), P=f(C), C=f(f(C)), or P=f(f(P)).

Note that the primative used in the mixing function f is not limited to XOR, it can ADD but the overal mixing function would need to complement one of the inputs usually the key K to K’ with respect to the cardinality of the alphabet (ie “two’s complement for binary power alphabets A). Thus C = P ADD K, and P = C ADD K’.

Where opinions diverge is with regards the key K and how it is generated.

For the OTP and similar provably secure systems each element of K, Ki is randomly selected and fully indipendent of every other Ki. That is “You DO put the ball back in the urn after drawing it”.

For other Stream Ciphers the generation process “has memory” thus the individual Ki whilst they may be randomly selected ARE NOT independent of each other. That is “You DO NOT put the ball back in the urn after drawing it, you wait untill the urn is empty and put all the balls back at the same time and start again.

Using this “With Memory” and “Without Memory” more restricted stream cipher distinction the OTP is not a Stream Cipher, even though the mixing mechanics are the same.

Importantly the “With Memory” key generation method, the fundemental size of the memory defines the “Key Space” size, not the “message length”. The opposit is true for the OTP where the generation method is unbounded and thus the message length defines the key space size for each and every message.

The system you described you say has a “small secret” that both parties know well that is what defines your systems keyspace size thus it is not an OTP.

Look at it this way, there are determanistic algorithms that can be used to generate some irrational numbers, they have memory requirments that grow with the length of the output. In effect they generate fractions where the memory required to hold the fractions grows with each iteration. So with pi it’s a effectively 2n where n is the number of digits you HAVE output so 3/1, 31/10 …. 31415926/10000000…

Now you could use such a generator to greate an endless stream of digits, but the number of such generators is limited. Thus you could use a second function to mix the last two or more digits output with a short secret.

But… Based on “the enemy knows the system” an attacker would know what your generator algorithm is, thus at worst they would only have to brut force the “short secret” space to have the plantext. Thus the issue moves from one of having an infinite length key generation recognition one, to a way of determining that you have a valid plaintext.

This depends on the statistics not of the key which is now irrelevant, but on the plaintext. Have a look at unicity distance and how it is calculated.

It’s why you should always “flaten the statistics” of your plaintext to reduce them as much as possible.

The usualy quoted but actually not very good way to do it is to use “dynamic loss less compresion”.

There are two basic types of lossless compression, dynamic and non dynamic. The both have advantages and disadvantages. Whilst dynamic compression will result in shorter messages in most cases the way it works requires a dictionary unique to each message be built and sent with or within the compressed plaintext. This dictionary “adds structure” which is an even bigger peg for a cryptanalyst to hang their hat on than ordinary language statistics, and such structure is easier to detect mechanically…

Thus if you are going to use compression to reduce message length, you need to still follow it with a way to “flatten the statistics” this time of the structure not the language. There are ways to do this such as some forms of fractionation.

Oh and remember that ALL forms of Error Correction “add structure” so should only be done on the ciphertext never on the plaintext.

Wandee • June 7, 2021 4:49 AM

Hi Mark,

Thanks for the lecture. It is well received and your suggestions taken onboard and you are correct in your statement, that more information is needed to evaluate an encryption system. However, that was not the question I had for you and for @weather, or was it? The question was based on a mathematical problem I put to you, if it was possible to determine a 2000 random character string which had been transformed into a cipher, using the 26 characters of the English alphabet. For @weather I reduced that to a problem using 4 bits and like you, he failed to give a simple answer. The answer should have been ‘No’ or ‘Yes’ and in case of the latter one, a mathematical proof would have been nice. That should have been followed up by the question how the system works and not with a conclusion from your end that it doesn’t work. I hope you follow the (patronizing) comments you made and open your mind to absorb much knowledge. If you can’t, then find some knowledgeable people who can help you, as we did during the course of the last five years (not the 5 or 10 minutes you suggested).

The death-end path as you called it, became our road and started at the Caesar cipher, leading to Leon Battista Alberti in the 15th century who inventing the Alberti Disk. Kahn credits him with the invention of the poly alphabetic substitution and in the 16th century multiple alphabets and code preceding encryption was added. Until the 19th century this offered a strong protection for ciphers. At the end of the 19th century it was Frank Miller and at the start of the 20th century Gilbert Vernam who independently invented the OTP.

Let’s have an example based on the Alberti Disk, but instead of having a second alphabet going from A to Z we use a permutation. Using only this permutation and reading from outwards ‘HELLO’ inwards our cipher becomes TVRRB. Obviously that is not safe and we change the modus by changing the permutation after each character encryption. From the 16th century we know that people used a character code to move the alphabet for each encryption step, but this code was limited and at the end of it would start with the first permutation again, if the plaintext length required it. Our changes will use the plaintext to create permutations, which means each plaintext character will have a unique permutation and during the process transform the plaintext into a random character string. The modus here is moving to the first plaintext character on the alphabet and take the characters on the permutation, placing them in reversed order at the end; creating the next permutation. The character at the start of this permutation becomes the first transformed plaintext character. H is replaced by L and modular arithmetic applied, with the first character of the first permutation. We move to the second plaintext character E and repeating the process. W becomes the next transformed plaintext character and is paired with the second character of the first permutation. Once all plaintext characters have been transformed and modular arithmetic being applied our cipher is IDUMM. An adversary knowing the system also knows that prior to encryption the first permutation is generated via a character code, which can be 0 to 4 characters in length. Let’s assume in our case these have been two characters, U and K and the data we transmit is UKIDUMM.

0 1 2 3 4 5 6 7 8 9……………………………………………..25
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
X H G N V A Q T L Z P R Y W B F U E I M K C D J S O H
L Z P R Y W B F U E I M K C D J S O T Q A V N G H X E
W B F U E I M K C D J S O T Q A V N G H X Y R P Z L L
O T Q A V N G H X Y R P Z L S J D C K M I E U F B W L
Z L S J D C K M I E U F B W P R Y X H G N V A Q T O O
R Y X H G N V A Q T O……………………………………………

TVRRB – single permutation mapping
LWOZR – multiple permutations; transformed plaintext + modular arithmetic = cipher
H.. | L + X = I
E.. | W + H = D
L.. | O + G = U
L.. | Z + N = M
O.. |R + V = M

Certainly you are a knowledgeable person as far as cryptography goes and I trust you have no problems to present us with a mathematical solution for the dilemma we face.
Before you answer (big if), keep in mind we can use the hexadecimal system or binary system for the initial secret we share (an option for users of our system). So all written languages and data formats could be possible solutions, be that ASCII or Unicode.

Here is a slightly different permutation at the start, resulting in the same transformed character string as in the example above. The plaintext here is WORLD.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
X R G N V A Q T J P W Y H Z B F U E O M K C D L S I

LWOZR

Wandee • June 7, 2021 4:56 AM

@Markh

The table got a bit out of shape, so here it is again

0 1 2 3 4 5 6 7 8 9 to 25
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
X H G N V A Q T L Z P R Y W B F U E I M K C D J S O
L Z P R Y W B F U E I M K C D J S O T Q A V N G H X
W B F U E I M K C D J S O T Q A V N G H X Y R P Z L
O T Q A V N G H X Y R P Z L S J D C K M I E U F B W
Z L S J D C K M I E U F B W P R Y X H G N V A Q T O
R Y X H G N V A Q .

1&1~=Umm • June 7, 2021 6:53 AM

@Wanadee:

“which means each plaintext character will have a unique permutation”

Is that each ‘a’ in the Alphabet set, or each ‘m’ in the message.

The importance is different.

If it’s each ‘a’ the cipher is polyalphabetic and thus repeates and alows the equivalent of a message in depth attack.

If it’s each ‘Mi’ then the purmutations never repeate and that reduces mathmaticaly to M simple substitution ciphers.

If the latter then the question then moves to how the permutations are selected.

If selected determanistically then if M is large the patterns will show eventually which enables prediction.

If random then there are no patterns to show thus no prediction is possible regardless of length.

What you appear to go onto describe is a determanistic process not a random one, which means it is breakable if M is long enough.

Does that answer your question?

Weather • June 7, 2021 9:46 AM

@wandee
Why does ‘fue’ repeat with each iteration just shifted to the left?

Weather • June 7, 2021 10:10 AM

@wandee
If I understand, if you have 1 billion sequence instead of 2000 but the plaintext is 1 million then the plaintext will make a signature onto the random cipher input, allowing both to be detected, by multiple plaintext or multiple cipher random bits, or filtering out the none random plaintext from the cipher by throwing random strings at the combined cipher output.
Yes it will leak.

MarkH • June 7, 2021 1:19 PM

@Wandee:

Roughly, any encryption scheme can be assigned to one of three classes of message secrecy, with respect to “data at rest”:

• Weak — an attacker could perform cryptanalysis (key discovery) within a feasible time frame and budget

• Strong — while cryptanalysis is possible in principle, the required time and resources make it infeasible to achieve … there is no practical attack

• Perfect — cryptanalysis is impossible, even with unlimited resources

Shannon proved that the Vernam cipher — and only the Vernam cipher — achieves perfect message secrecy.

Every cipher with a key smaller than the message — there are no exceptions to this! — can be cryptanalyzed (if all else fails) by exhaustive search of the keyspace. For modern ciphers exhaustive search is infeasible, but not theoretically impossible. Only the Vernam cipher can never be cryptanalyzed, even in theory.

Therefore, a cipher requiring the “exchange of a small secret” can never, never, never achieve perfect secrecy if the message volume is larger than that small secret. Insisting that such a scheme has perfect secrecy is proof of failing to understand Shannon’s paper.

Having disposed that any such scheme like the one you have outlined cannot be in the Perfect category, it is either Weak or Strong.

Most Strong ciphers in broad usage (like AES) have been broken in the narrow technical sense that researchers have found attacks less costly than exhaustive search … but for Strong ciphers, these attacks are still many orders of magnitude beyond any imaginable effort, and often require predicates which would be impossible to achieve in most usage scenarios.

I am most confident that the scheme you have in mind is Weak — if it were used for any large message volume, it could be cryptanalyzed at a cost of perhaps a few dollars, or even a few pennies.

People who design strong ciphers (Bruce is the only person here I know to have done so) start by intensive study of the art and science of cryptanalysis, which is deep and difficult.

Who would create a strong cipher, had best begin by breaking as many ciphers by other people as they can manage.

Who would encourage people to use a newly invented cipher, had best make an extremely solid and convincing case why it’s better for them than what is already in use. That case must include assessment by experts in cryptanalysis, who made a large investment of time to study various attacks, and have assessed that the best practical attack is at least billions of times more costly than even a nation state could afford.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.