Compromised TLS Certificates

The Indian CA eMudhra Limited has eight TLS certificates with laughably weak private keys:

The compromised eMudhra keys were defective at a level that’s challenging the imagination of many of the engineers studying the incident. A normal size for a NIST P-384 elliptic curve cryptography private key contains roughly 384 bits of entropy, a size allowing almost 2384, or a number with 116 digits, different possibilities. The private key sizes of the compromised keys ranged from 3 to 8 bits. Astonishingly, the private keys were 4, 56, 66, 115, 155, 156, 230, 237.

“That is extremely in the ‘this should not be possible’ category,” Valdorda said. “Maybe some horribly dangerous key generation interface has a ‘size’ parameter and they set it to 1 by mistake???”

Ben Cartwright-Cox, director of BGP.tools, said: “My guess is that it’s example code that accidentally leaked to production, but hard to know. But it’s bonkers that no one noticed.”

At this early stage, the most immediate threat appears to be for those using VPNs, especially in countries with governments likely to maliciously intercept traffic. There are likely many other cases for concern. End users largely have no recourse other than to hold off using many non-browser forms of TLS communication until they receive assurances updates are in place.

The whole certificate regime has long been a mess:

The incident is the latest to expose a fatal flaw in the TLS regimen. It’s only as strong as its weakest link, which in this case was eMudhra. Fortunately, transparency logs account for much of that failure, but this measure requires parties to actively monitor massive feeds and works only after unauthorized certificates have been issued. eMudhra representatives weren’t immediately available to answer questions.

One caveat: exploiting compromised certificates requires an active adversary-in-the-middle attack, meaning the attacker must act as a proxy between two TLS parties and receive encrypted traffic, decrypt it, reencrypt it, and send it to the other party. Such capabilities, in some cases, are usually limited to only the most well-resourced attackers. People with control of a local network­at a coffee shop, university, or other organization­face much less of a challenge.

Cleanup of this is going to be another mess—and it’s right on top of the PHP vulnerabilities.

Some more information.

Posted on October 23, 2026 at 7:04 AM • 32 Comments

Comments

Clive Robinson • October 23, 2026 9:34 AM

@ Bruce, ALL,

With regards,

“… has eight TLS certificates with laughably weak private keys”

It may be more than eight.

If you go to,

‘https://emudhra.we-have-a-problem.com

It now shows 14 certs to be tested, yesterday afternoon UK time it was 12…

But the reality is that atleast 60million or so certs 3Mudhra signed are now garbage.

But also as many as cyber-attackers want to generate.

Because there are way way to many embedded and similar systems that will never get their cert files upgraded…

This is a problem that is not going to go away for years.

As for the article saying,

“NIST P-384 elliptic curve cryptography private key contains roughly 384 bits of entropy, a size allowing almost 2384, or a number with 116 digits, different possibilities.”

Anyone else thinking it does not take the “leading zeros” issue into the math?

Bcs • October 23, 2026 9:43 AM

This incident reenforces the argument that it should be easy to revoke certificates. Both in the mechanism for propagating CRLs quickly and widely as well as in setting things up so that the “economics” favor doing so quickly if there’s even a reasonable suspicion that it is justified.

One change that would facilitate the second part would be to adjust TLS processing so that reporting cert chains to multiple root CAs is both supported and expected, so that it would take multiple revocations to take down sites. (I haven’t actually looked in detail, but I think that could be accomplished by simply expecting TLS clients to ignore “extraneous” certs provided during the handshake.)

Clive Robinson • October 23, 2026 10:00 AM

@ Bcs, ALL,

With regards,

“This incident reenforces the argument that it should be easy to revoke certificates.”

It would be nice if it were not for the flip side of “Censorship” and taking away “Individuals rights”.

We are moving very rapidly into “Authoritarian times” in which the “common truth” gets killed off and replaced by Government or Corporate faux-truth.

For instance if you have a current Android OS phone if you go to the

‘https://emudhra.we-have-a-problem.com

Site and get green across the board what is it actually telling you?

Yup Google has fritzed with your phone and you were not aware of it…

Now consider what Google is going to do in just a few weeks time,

https://arstechnica.com/gadgets/2026/03/with-developer-verification-googles-apple-envy-threatens-to-dismantle-androids-open-legacy/

D • October 23, 2026 10:25 AM

There is more detail on this, including comments from eMudhra engineers, on the Mozilla issue tracker: https://bugzilla.mozilla.org/show_bug.cgi?id=2083449

It looks like they were using the correct HSM device for keys, but the script they used to handle the key generation was not actually using the HSM device for key signing. Looks like a simple enough mistake.

Although it would have been trivial for them to detect this if they had attempted to use the HSM to validate the intermediate after cross signing. As they inadvertently signed their intermediate with the incorrect root cert they would have spotted this immediately.

Clive Robinson • October 23, 2026 10:56 AM

@ Bruce, ALL,

This has popped up,

eMudhra to Exit global SSL/TLS Certificate Business

Will Sharpen Focus on Core Enterprise Solutions and trust services other than SSL/TLS

“BENGALURU, INDIA, October 22, 2026 – eMudhra Limited (BSE: 543533 | NSE: EMUDHRA), a global digital trust company, today announced that its Board has decided to voluntarily withdraw from the global SSL/TLS certificate business.

Mr. V. Srinivasan, Chairman, eMudhra Limited referred to the recent incident relating to its global SSL/TLS certificate and indicated that eMudhra handled the recent incident diligently, revoking the affected CAs within 14 hours of discovery and disclosing promptly. There were no end entity certificates issued out of the affected CA’s. Its infrastructure was not compromised and no data was breached. All physical and logical security controls remained intact.

He added that global SSL/TLS is a small part of eMudhra’s business contributing to about 1% of the global revenue. Due to increasing data sovereignty & compliance requirements, complexity and cost associated with this business is increasing over the years. This, paired with the fact that some of the large entities issue the SSL/TLS free of cost, the business potential and RoI of this line of business also has considerably reduced for eMudhra when measured against our cumulative revenue base.“

https://emudhra.com/en/press-release/emudhra-to-exit-global-ssl-tls-certificate-business

Bcs • October 23, 2026 1:04 PM

@Clive Robinson

That just argues for there not being a single point of authority for the PKI. Neither a single global one or a requirement that user limit themselves to choosing a single one.

Devices being able to choose one or more independent CRL publishers also works to mitigate state run MitM and sites being able to be verified by multiple independent root CAs limits the censorship/DoS impact of revoking any one CA.

Clive Robinson • October 23, 2026 2:58 PM

@ Bruce, ALL,

From,

https://bugzilla.mozilla.org/show_bug.cgi?id=2083449

You might want to note,

“6 of the impacted certificates are for TLS and trusted by the Chrome, Mozilla, Microsoft and Apple root programs. The other two certificates are for codesigning and trusted by Microsoft”

Note “codesigning” it’s important especially when you add from further down,

“No response from Microsoft”

I do not know what the current status is but having world wide open Codesigning keys on the Western Worlds most used Consumer and Commercial OS…

Is how do I put it “not exactly desirable”.

Whilst you would have to mount a supply chain or specialised MITM attack to exploit it, we have seen such before.

Clive Robinson • October 23, 2026 4:02 PM

@ Carl Fink, ALL,

With regards,

“And yesterday, the node.js vuln…”

Is just one of several that would have been “Newsworthy” if not for this eMudhea and PHP debacles.

For instance, gears about this one?

https://www.theregister.com/security/2026/10/22/max-severity-gitlab-bug-allows-remote-code-execution-over-12-years-of-releases/5304854

Once that would have rated a “five alarm” rating, currently barely a bleat.

Some quarter of a century ago on Sept 11 a UK Political Side kick “SpAd” –jo moore[1]– got in really hot water with her Email that said,

“It’s now a very good day to get out anything we want to bury.”

https://www.theguardian.com/politics/2001/oct/09/uk.past

Due to the time she sent it (after second crash but before any colapse) she would have got away with it. However not long after she got accused of doing it again even though the evidence had been “faked-up” by a Civil Servant she was forced to resign.

Since then the phrase,

“A good day to bury bad news”

has become a sort of meme being used to refer to other instances of attempting to hide one item of news behind a more publicised issue.

As far as I’m aware that’s not what is actually happening with these other ICTsec issues. But it does demonstrate how the News/Media works.

[1] jo Moore is about the same age as our host @Bruce and she clearly had political aspirations, but also was apparently to confrontational with certain proven to be malicious Civil Servants who basically did an “Et tu brute” on her as part of going after her boss. She effectively disappeared from sight and the last heard of her far as we know was with the BBC reporting she was training to became a primary school teacher at Muswell Hill Primary School in north London.

hehe • October 23, 2026 4:04 PM

Clive writes, Yup Google has fritzed with your phone and you were not aware of it…

Oh but I was aware of it. Google initiated a silent background update to my phone last night but I caught it in the act because my firewall caught it. I figured that’s what was going on so I let it pass.

Most people are not aware that Google can effectivly take over your android phone but that’s ok because as much as I hate Google I still trust it more than the alternatives.

freedom • October 24, 2026 10:57 AM

Google can effectivly take over your android phone

They effectively take over the phone from the moment their malware O.S. is installed. So you are using a misleading verb tense. The google-NSA criminals can and do take over the phone.

Also, it is not your phone. You do not control it at all, you do not own it at all.

but that’s ok

It’s ok for the anti-human party and not ok for humanity.

Ismar • October 25, 2026 5:26 AM

There appears to have been a missing technical safeguard that could have caught the error immediately. A fundamental security control—an automated check to verify that a newly generated private key is actually strong and random—seems to have been absent or failed. The ease with which researchers later recovered the keys in “under a second” proves how catastrophically weak they were.‌‌

Clive Robinson • October 25, 2026 6:43 AM

@ Ismar, ALL,

With regards,

“an automated check to verify that a newly generated private key is actually strong and random”

If you think about it that’s not going to fix this problem (but it might others).

Because the mathematics of the transform from input to output, makes testing “newly generated” output not of any real use in this case.

The testing should be done on the supposedly randomly selected number that will become the input to the mathematical transform.

Something few think about is that many randomly selected numbers are really not suitable.

Think about the number range that fills a byte. Half of them are a inverse for the other half. But also consider half those random numbers have a leading zero that in reality makes them 7bit numbers not 8bit. Of those 7bit numbers half are really 6bit numbers for the same reason and so on. There are other things like unwanted structure. Consider the case of the top half of the bits being set and the bottom half clear and similar that comprise the base Walsh transform waveforms.

All of these are in effect “weak numbers” in some way…

The mathematical transform can make weak numbers look strong to most tests, even though in reality they started out weak even very weak.

It’s part of them being “One Way Functions”, but there is actually no usable proof that what are considered deterministic “One Way Functions” actually are “One Way”. In fact the One Way Functions with Trapdoors cryptography uses tends to suggest that there might not actually be true deterministic One Way Functions. That is they are fully or partially reversible under certain “known conditions”.

anaoymouse random • October 25, 2026 2:28 PM

Think about the number range that fills a byte. Half of them are a inverse for the other half. But also consider half those random numbers have a leading zero that in reality makes them 7bit numbers not 8bit. Of those 7bit numbers half are really 6bit numbers for the same reason and so on. <

From the point of view of an attacker attempting to guess a key, a leading 0 is no different from a leading 1, unless the key has a pathological structure that creates such a linkage. That 0..255 can be represented as -128..127 also has no bearing on a key's entropy.

Jonathan Wilson • October 25, 2026 4:51 PM

Why haven’t solutions like DANE taken off? If I understand how it works, the idea is that DANE puts SSL/TLS keys (or something that can be used to validate SSL/TLS keys as genuine) in DNS records and digitally signs them with keys that go all the way to the DNS root.

blaziken • October 25, 2026 7:09 PM

@Clive:

“consider half those random numbers have a leading zero that in reality makes them 7bit numbers not 8bit.”

I don’t see that this is the case, as you seem to be suggesting that leading zeros shorten the number. This might be true when we write a number down in our numbering scheme, but it still takes the full byte to store.

Indeed, writing the number with a leading zero can cause confusion because this conventionally indicates octal representation.

Your reasoning reminds me of the “unexpected hanging paradox”, but I can’t think why.

Clive Robinson • October 25, 2026 8:41 PM

@ blaziken,

You say,

“I don’t see that this is the case, as you seem to be suggesting that leading zeros shorten the number. This might be true when we write a number down in our numbering scheme, but it still takes the full byte to store.”

Which is the root of the problem, because it effects more than “storage” it also effects “perspective” and that is problematical,

You go on to say,

“Your reasoning reminds me of the “unexpected hanging paradox”,”

On the Wikipedia page you will find,

“There is no consensus on its precise nature and consequently a canonical resolution has not been agreed on. Logical analyses focus on “truth values”, for example by identifying it as paradox of self-reference. Epistemological studies of the paradox instead focus on issues relating to knowledge; for example, one interpretation reduces it to Moore’s paradox. Some regard it as a “significant problem” for philosophy.”

It is about “expectation, consensus and factuality”.

One example is to do with the apparently simple question of “What is the time?”

Which can be a cover for one of several questions

1, What is the factual time.
2, What is the consensus time.

Consensus time is “geo-political” covered by “Civil time” and factual time is specific to “your actual position with regards a reference point”. Whilst the former is a “lie of convenience” the later is actually different for anyone not on your meridian normal to the plain of rotation with regards to the reference point you are using.

Which due to yet more “unexpected synchronicity” has in the past couple of hours been talked about as a pod cast you can watch,

https://m.youtube.com/watch?v=uNQewqqghWs

The point is almost every time “consensus” produces a “lie of convenience” which is sometimes jokingly called “A first approximation” or in Australia from America the now sarcastic,

“Good enough for government work!”

https://grammarist.com/idiom/good-enough-for-government-work-and-close-enough-for-government-work/

The thing is unless the first and second parties around the asked question are using the same context mostly the answer given will be wrong.

Hence if you are thinking in terms of “storage” and I’m talking about algorithms that are effectively about working with a set of integers used as “natural numbers” for “counting in a range” the context will be different and thus the expectations will differ.

Clive Robinson • October 26, 2026 5:30 AM

@ Kris Olejniczak, ALL,

“Every step of the process was evidenced. Nobody evidenced the output.”

Err not quite,

For security reasons nobody evidenced the input to the process… Possibly because the system design prevented it.

That is nobody looked at the random numbers going into the key making algorithm in the way necessary.

It is why it is not so unusual for the more cautious to as a minimum,

1, Check the bit ratio of ones and zeros in the random number.
2, Check the set and clear bits distribution within the random number.
3, Check for “repeated runs” in the bit patterns.
4, Check the “fine structure” in the bit patterns.

As part of the random number generation process to check a “True Random Number Generator”(TRNG) output is neither broken or being externally influenced in some way[1]. Or worse internally broken as part of the design process which has been shown[2].

It’s fairly clear that none of the “inputs” to these certificates had been checked.

But what should be of more interest is how the person who “discovered” these eight random numbers found them?

I suspect there might just be an interesting back story to that, which is yet to honestly and believably told…

[1] If you look back on this blog you will find discussions on never using “on chip TRNGs” because they,

1, Do not allow access to the raw generator output so can not be checked.
2, Use a cryptographic algorithm to hide the many many weaknesses such on chip TRNGs have.
3, Use some form of chain mode such that “basic substitution” by the crypto algorithm is not obvious.
4, That originally the crypto algorithms proposed or used were actually weak.

Originally the worst offender at this was “Intel”…

Even Linus Torvalds got attacked over the proposals to drop what were seen as security measures by others and switch to using just the on chip TRNG and he later apologized for his abruptness over the issue.

To see another perspective on just a part of this,

https://www.nccgroup.com/research/on-linux-s-random-number-generation/

[2] Many early on chip TRNGs used “ring oscillators” with the outputs getting “mixed” in some way. The problem with this is each “ring oscillator” has a nominal or mean frequency of oscillation. If you mix the outputs of oscillators you get the sum and difference frequencies in the output of the mixer. Even though it’s digital and looks close in to be random, it’s anything but. It’s actually a one bit oversampled signal of the difference frequency as a very pure sinewave. The fact it looks entirely random “close in” is because of various effects one being the difference frequency and sampling frequency do not have common harmonics. However pull the timebase out, you can see by the intensity patterns that there is very definitely a digitised sinewave. I’ve talked about this on this blog a number of times in the past, and few if any have done the simple “graph drawing” that shows just how true it is.

So to attack the system all you need to do is work out the “frequency and phase” of the ring oscillators that is actually not that difficult to do with the oversampled waveform. So a crypto algorithm is used to try and stop you doing this… But what if you “know the key” being used… Which the chip designers and probably SigInt agencies would know…

freedom • October 26, 2026 1:54 PM

Think about the number range that fills a byte. Half of them are a inverse for the other half. But also consider half those random numbers have a leading zero that in reality makes them 7bit numbers not 8bit. Of those 7bit numbers half are really 6bit numbers for the same reason and so on.

But that has nothing to do with a given value being “random”, or not. A “random” value is a value that you can’t predict. That’s all. 00000000 is as random as 01010101 or any other 8bit value.

Of course in the case of crpytographic keys you need a value that the attacker can’t predict. And apparently you can get such values by measuring noisy voltages, like say zener voltages.

Clive Robinson • October 26, 2026 6:15 PM

@ freedom, ALL,

You say,

“A “random” value is a value that you can’t predict. That’s all.”

But you also said earlier,

“That 0..255 can be represented as -128..127 also has no bearing on a key’s entropy.”

You really have got that wrong.

I quite deliberately said “half” because it’s “unbiased” where as “-128..127” is biased to a mathematical algorithm…

You are using a 2’s complement number that is biased 128:127 it’s a small bias ~0.7874% but a bias nether the less because there is only one zero.

A 1’s complement number on the other hand is not biased in that way because it has two zeros. But having two zeros causes other complications in mathematical algorithms.

It’s why I explained to @blaziken,

“The thing is unless the first and second parties around the asked question are using the same context mostly the answer given will be wrong.

Hence if you are thinking in terms of “storage” and I’m talking about algorithms that are effectively about working with a set of integers used as “natural numbers” for “counting in a range” the context will be different and thus the expectations will differ.”

As for,

“And apparently you can get such values by measuring noisy voltages, like say zener voltages.”

I’m guessing you just “read and repeated” that… And have never built and tested to the required accuracy.

Zener devices such as certain types of reversed biased junction diodes have issues. I won’t go into them here but just remember that some have nonlinear behaviour and that has curious effects.

Further, not all diodes sold as Zener actually use the Zener effect. Low voltage diodes tend to use quantum tunneling and higher voltage the avalanch effect. So as a rough rule of thumb less than 5V zener, above 5V avalanche. Oh and board layout and other component selection can stop it being “white noise (equi frequency/power spectrum).

freedom • October 26, 2026 7:42 PM

Clive,

I only made one post, but granted I’m making the same point “anaoymouse random” made. The fact that we can see some kind of bit pattern in a random byte doesn’t mean anything as far as randomness is concerned.

I’m guessing you just “read and repeated” that…And have never built and tested to the required accuracy.

I had to take a look at my notes. I was misremembering, the circuit uses a reverse biased transistor in avalanche mode. Anyway, what I was getting at is that while something like Intel’s TRNGs can’t be trusted at all, people can easily build their own. But then again, computer security remains a disaster even if you have a working true RNG.

ResearcherZero • October 28, 2026 5:20 AM

Microsoft has released OOBE patches for devices that do not receive automatic updates. The updates need to be installed manually to take effect and remove the offending certificates.

SSL/TLS certificate forgery allows site impersonation and man-in-the-middle interception. The compromise of the keys would allow anyone who posses them to issue forged certificates.

Google and Apple are releasing updates for Emudhra certificates. Apple has also released instructions for how to remove the certificates. Emudhra has quit the certificate game, and its failure to use the correct signing key to sign one of its root TLS certificates does not provide much confidence in the standards practiced within the firm.

https://bugzilla.mozilla.org/show_bug.cgi?id=2083449#c7

An incident review from 2025 by eMudhra states that they did not see an email for CA revocation.

By law, certificate issuers are obliged to adhere to secure and auditable practices. Exiting the certificate provider market should not be an option that allows a firm to escape independent audit and inquiry into practices and procedures within a company. A complete audit trail must be maintained.

https://bugzilla.mozilla.org/show_bug.cgi?id=1970728#c2

Clive Robinson • October 28, 2026 9:06 AM

ResearcherZero,

It’s nice to hear,

“Microsoft has released OOBE patches for devices that do not receive automatic updates.”

It’s finally a bit of well overdue “Thumb Out Of Bum”(TOOB) activity from Microsoft.

Unfortunately the Microsoft Windows “Out-Of-The-Box (OOBE) updates that have been gaining prominence have user security issues of their own.

In part because Microsoft has been moving “in it’s view” to increased security and OS fine-tuning (read as “lock-in and rent-seeking” by AI and on computer software lock-out etc).

But… this has ment fundamental changes to the Windows initial start up and set up phases, which is the point equivalent right when the computer, is in the “just installed” for the first time or after a factory reset and is as vulnerable as it’s ever been since the “get go”.

Thus many see it as being not due to increasing security, but minimising issues for MicroSoft forced on the user revenue raising, directly or indirectly.

Especially as OOBE is the equivalent of the “Setup Wizard” that appears immediately after starting a brand-new computer or after a factory reset which in later versions of Win OS forces you back down Microsoft’s chosen anti-privacy “surveillance path”. Because during OOBE, you not only have to reselect your language and region information and reconnect to the network, and adjust basic user preferences thus fingerprinting. It also triggers enrollment and configuration processes with “the corresponding management platform” which for many is Microsoft’s “surveillance system” where everything goes up to the Microsoft servers and forced OS Upgrades.

All that aside it does not mention if it has cleaned up the two “Trusted Code Signing” issues…

Mailman • October 28, 2026 7:29 PM

“A normal size for a NIST P-384 elliptic curve cryptography private key contains roughly 384 bits of entropy, a size allowing almost 2^384, or a number with 116 digits, different possibilities.”

I am certainly not going to defend eMudhra’s weak key generation practices, but if we’re going to argue that a 384-bit private key is secure because of how many possibilities it represents, I would point out that 4 is one of them.

anonymouse random • October 29, 2026 1:52 PM

I am certainly not going to defend eMudhra’s weak key generation practices, but if we’re going to argue that a 384-bit private key is secure because of how many possibilities it represents, I would point out that 4 is one of them.

That argument ignores the fact that the probability of a randomly-generated 384-bit key assuming an easily-guessed value like 4 is only a few in 2^384. Also the argument says too much, because even an infinitely-long key could still assume an easily-guessed value.

Clive Robinson • October 29, 2026 5:51 PM

@ Mailman, ALL,

You say,

“Also the argument says too much, because even an infinitely-long key could still assume an easily-guessed value.”

You are talking about “value” which really is not what you should be talking about when looking for entropy.

“4” is just a single bit set in an array or set of 384 bits and thus the same as the values 1,2,4,8,16,32 … 2^383.

Now consider every other bit set or clear you get a …1010… pattern circularly left or right shift as many times as you want you only end up with …1010… or …0101… And no change in the set/clear bit ratio thus the entropy must be the same.

So likewise the “value creating position” of the single set bit does not effect the bit entropy of the array derived from the set/clear patterns the bits form.

If you read through the literature you will find that the “bit patterns” not the “integer value” is what is discussed with “Digital Random Bit Generators”(DRBGs) and the entropy.

After testing the set/clear bit ratios and pattern runs a low water entropy value is found.

That is the “integer value” has only minimal effect on “entropy” as it’s,

“The bit pattern not the integer value”

That actually counts. Which when you think about it as bits emerging as fully independent entities with a bit to bit state change only being 50%.

As you go into “hash algorithms” you will see this 50% bit to bit become the “Avalanche effect” where a change of one bit at the input on average will change 50% of the bit states at the output.

Only much further down the line does “value” have any meaning and that is for “arithmetic operations with carry” not “logical operations without carry”. Think of it as the difference between ADD and XOR.

The difference between logical and arithmetic operations becomes more obvious when you talk about “hash algorithms”, “checksums”, “addition” and “multiplication” of “bag of bits”(BOB) arrays.

Winter • October 29, 2026 6:15 PM

@Clive

“4” is just a single bit set in an array or set of 384 bits and thus the same as the values 1,2,4,8,16,32 … 2^383.

When you try to seriously define the “probability” of a finite bit string, you will end up in Kolmogorov complexity.

The bit expansions of Pi or Euler’s number e look random to every test. However, they can be generated by simple, short algorithms. They have low Kolmogorov complexity. The number “4” is algorithmically simple, hence it is high “probability”.

And we know Kolmogorov complexity is uncomputable. Hence, the “probability” of a key is non-computable.

Clive Robinson • October 29, 2026 7:57 PM

@ Winter,

With regards,

“And we know Kolmogorov complexity is uncomputable. Hence, the “probability” of a key is non-computable.”

It is and it is not, it depends on how you count your states.

We know for instance there is a “high water” limit on states for every “bag of bits” array formed of M integers of N bits each. In essence it’s (M.N)^2. Similar reasoning applies to all fixed size arrays.

This is a high water limit on the maximum number of bit states of unassigned meaning. However such arrays although common are in fact degenerate and limited. Worse in practice as meaning is assigned the number of used states drops quite quickly.

Hence the reason nearly all strings even if randomly created are compressable in any number of ways.

Worse let us assume there is more than one way to compress based on say,

1, Individual character frequency.
2, Length of repeated character patterns.

It often comes as a surprise to many people there is no way to know the optimal order to apply the compression methods to get maximal compression.

I could go on indicating why compression methods can almost never be optimal by just viewing the data. You actually have to do all the combination of methods to find out.

It’s a subject that although apparently simple has a complexity that grows rapidly for little return.

It’s why I let others mark out the domain space in books and papers such as,

https://arxiv.org/pdf/2002.07674

From more than a couple of decades ago.

Winter • October 30, 2026 3:08 AM

@Clive

It’s a subject that although apparently simple has a complexity that grows rapidly for little return.

Indeed, you inevitably run into the weeds when you push hard enough.

But to crack a key, you start searching at the low Kolmogorov complexity side of the pool.

Clive Robinson • October 30, 2026 10:50 AM

@ Winter, ALL,

Other key sizes way smaller than search size or too predictable…

It would appear that having tiny size for keys is more common than you would hope,

The case of the 9 bit AES key

Several PDF implementations advertise AES-256, but generate the 256-bit key from either a very small state space, or from insecure random sources.

“We found that several PDF implementations generate their AES-256 file keys from state spaces small enough to enumerate. In MuPDF, only 9 bits of random state affect the actual AES-256 key. Other PDF editors like Foxit base their AES-256 key on time based randomness and thus also lead to keys that are trivial to recover.“

https://v12.sh/blog/the-case-of-the-9bit-aes-key

I wonder how many more will pop up much to the shock of people who have trusted the app suppliers…

Worse how many will now get found by AI on go faster commands…

Leave a comment

Blog moderation policy

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.