Entropy, a CLI that scans files to find high entropy lines (might be secrets)
github.com
github.com
perl -lne 'next unless $_; $z = qx(echo "$_" | gzip | wc -c); printf "%5.2f %s\n", $z/length($_), $_'
It did react to this line
return map { $_ > 1 ? 1 : ($_ < 0 ? 0 : $_) } @vs;
I'm on the go but it would be interesting to see comparisons between the Perl command and this tool. The benefit of the Perl command is that it would run out of the box on any non-Windows machine so it might not need to be as powerful to gain adoption.
Thankyou for continuing the tradition.
xz or zstd may be better choices, or you can look at Hutter Prize [1] winners for best compression and therefore best entropy estimate.
That's a good point. But the Hutter Prize is for compressing a 1 GB file. On inputs as short as a line of code, gzip doesn't do so badly. For a longer line:
$ INPUT=' bool isRegPair() const { return kind() == RegisterPair || kind() == LateRegisterPair || kind() == SomeLateRegisterPair; }'
$ echo "$INPUT" | gzip | wc -c
95
$ echo "$INPUT" | bzip2 | wc -c
118
$ echo "$INPUT" | xz -F xz | wc -c
140
$ echo "$INPUT" | xz -F lzma | wc -c
97
$ echo "$INPUT" | zstd | wc -c
92
$ INPUT=' ASSERT(regHi().isGPR());'
$ echo "$INPUT" | gzip | wc -c
48
$ echo "$INPUT" | bzip2 | wc -c
73
$ echo "$INPUT" | xz -F xz | wc -c
92
$ echo "$INPUT" | xz -F lzma | wc -c
51
$ echo "$INPUT" | zstd | wc -c
46Which would require the dictionary as a separate input when decompressing, of course?
It also has vastly superior compression and performance, compared to gzip, even without.
The approach is simple: Turn the file into a stream of tokens. For each token, ask a language model to generate the full set of predictions based on context, and sort based on likelihood. Look where the actual token appears in the sorted list. Low entropy symbols will be near the start of the list, and high entropy tokens near the end.
I suspect most language models would deal with your alphabet example just fine, while still correctly spotting passwords and API keys. It would be a fun experiment to try!
Password: postgres
However, as our methods of predicting text improve, this number is revised down. LLMs ought to have made a serious dent in it, but I haven't looked up any newer results.
Anyway, all of this to say is that which words are chosen matters, but how they are put together matters perhaps more.
First of all, how to define "entropy" for text is a bit unclear in the first place. Here it's as simple as `-Sum(x log(x))` where x = countOccurences(char) / len(text). And that raises a lot of questions about how good this actually works. How long string needs to be for this to work? Is there a ≈constant entropy for natural languages? Is there a better approach? I mean, it seems there must be: "obviously" "vorpal" must have lower "entropy" than "hJ6&:a". You and I both "know" that because 1) the latter "seems" to use much larger character set than natural language; 2) even if it didn't, the ordering of characters matters, the former just "sounds" like a real word, despite being made up by Carroll. Yet this "entropy" everybody seems to use has no idea about any of it. Both will have exactly the same "entropy". So, ok, maybe this does work good enough for yet-another-github-password-searcher. But is there anything better? Is there more meaningful metric of randomness for text?
Dozens of projects like this, everybody using "entropy" as if it's something obvious, but I've never seen a proper research on the subject.
Anyway, that doesn't really answer my question. To summarize answers in this thread, I think PhilipRoman has captured the essence of it: strictly speaking, the idea of entropy of a known string is nonsense. So, as I suspected, information theory definition isn't meaningfully applicable to the problem. And as other commenters like you mentioned, what we are really trying to measure is basically Kolmogorov complexity, which, strictly speaking, is incomputable, but measuring the compression rate for some well-known popular compression algorithm (allegedly) seems to be good enough estimate, empirically.
But I think it's still an interesting linguistic question. Meaningful or not, but it's well defined: so does it appear to work? Are there known constants for different kinds of text for any of these (or other) metrics? I would suspect this should have been explored already, but neither me, nor anybody in this thread apparently has ever stumbled upon such article.
Regarding a prime as having higher entropy / less structure than say a perfect square or highly divisible number
a prime is a prime in any base, but the number of divisors will differ in non-primes, if the number is divisible by the base then it may appear to have more structure (smaller function necessary to derive, kolmogorov style),
does prime factorization have anything to do with this? i can almost imagine choosing a large non-prime whose divisibity is only obvious with a particular base such that the base becomes the secret key - base of a number is basically specifying your dictionary, no?
The problem of finding factors is only complex when you're asking about relatively big factors. If you're looking for constant or log sized factors you can just do trial division and find them.
Not necessarily the same number of digits, when changing the base the number of digits may change as well. E.g., decimal 8 becomes 1000 in binary.
My mind drifted towards Fourier transform. Using the transform as a way of describing a system with less entropy?
Or am I butchering all of mathematics by making this comparison?
Could you please present an example of this?
There are of course statistical tests like https://en.wikipedia.org/wiki/Diehard_tests, which are good enough for distinguishing low entropy and high entropy data, but current pseudo-random number generators have no problem passing all of those, even though their actual "entropy" is just the seed plus approximate the complexity of the algorithm.
There’s no requirement that the K-complexity is measured in a human centric language. Arguably all compression formats are languages too, which can be executed to produce the decompressed result. They are not designed to be human centric at all, and yet they do a surprisingly decent job at providing an estimate (well, upper bound) on Kolmogorov complexity. - As we can see in this program.
- trufflehog: https://github.com/trufflesecurity/trufflehog
- detect-secrets: https://github.com/Yelp/detect-secrets
- semgrep secrets: https://semgrep.dev/products/semgrep-secrets -- (Paid, but may be included in existing licenses in some cases
I think these solutions are all much better for finding secrets than something naive based on entropy. Yes, entropy is more general but these are well established tools that have been through the fire of many, many data sets.
[0] https://news.ycombinator.com/item?id=13304641
[1] https://www.splunk.com/en_us/blog/security/random-words-on-e...
Certain tools are more likely to be used by people working in spaces where they should/must be less trusting.
If there was a tool (there is) to scan my platform deployment against some NCSC/NSA guidance for platform security, and I wanted to use it, I'm likely operating in a space that should consider being cautious about running random tools I find on the internet.
The idea that whether or not it needs scrutiny is impacted by your goals with the software is... creative
I'll also create a docker image.
I just didn't expect this much popularity so the repo isn't 100% ready te be honest
If people want to run it isolated, the docker image is of course still a nice to have and docker hub is a convenient distribution mechanism. At the same time, an equivalent image can equally easily be created by the consumer.
Personally, due to trust, I would anyway still build it from source and run in a container, to be on the safe side.
Encrypted files do not compress well compared to code, I saw a phd thesis that postulated an inverse ratio of compression efficiency to performance data mining, this would be the opposite
Would be cool if this CLI could have a flag to read .gitignore and exclude all of the contents automatically.
Also it might be cool to have different strategies for detecting secrets, e.g. Kolmogorov complexity as other comments have noted.
This package seems to be measuring entropy by counting the occurrences of each character in each line, and ranking lines with a high proportion of repeated characters as having low entropy. I don't know how closely this corresponds with the precise definition. Source: https://github.com/EwenQuim/entropy/blob/f7543efe130cfbb5f0a...
More: https://en.wikipedia.org/wiki/Entropy_(information_theory)
And it fails for passphrases like 'correct battery horse staple', which have a large enough total entropy to be good passwords, but have a low entropy per character.
If the password system uses argon2 with a high memory requirement, you're in an even better position
But go on, use a 52 bit password – see what I care. But don't come crying to me when an institution with the smallest amount of funding was able to crack your vault.
Otherwise, I agree.
Adding random punctuation helps with the former, but might interfere with the latter. (In the extreme case, you just generate completely random strings character for character. That's the most secure, but the least memorable.)
key word here, I think we agree ;)
If you properly encode your secret it will have the entropy of its surroundings.
For example you can hide a string of entropy (presumably something encrypted) in text as a biased output of an LLM. To recover it you would use the same LLM and measure deviations from next-token probabilities. This will also fool humans examining it as the sentence will be coherent.
(Doesn't still stop smart people from committing fraud, but that is a different story.)
is it a cargo cult? it works for coca cola so maybe if we just spend a little more we'll see returns...
It's no nonsense, just catvideo and porns.
Are you proposing that they're really only posted as a medium for encoding something else that we're not privy to? If so, somebody took my idea.
Then, having done all that, such steganography may be detectable using this very tool by encoding the difference between the LLM's prediction and ground truth, but searching for substrings with low entropy instead!
Here's how I would do this:
Use some LLM, the weights need to be know to both parties in the communication.
Producing text with the LLM means repeatedly feeding the LLM with the text-so-far to produce a probability distribution for the next token. You then use a random number generator to pick a token from that distribution.
If you want to turn this into steganography, you first take your cleartext and encrypt it with any old encryption system. The resulting bistream should be random-looking, if your encryption ain't broken. Now you take the LLM-mechanism I described above, but instead of sampling via a random number generator, you use your ciphertext as the source of entropy. (You need to use something like arithmetic coding to convert between your uniformly random-looking bitstream and the heavily weighted choices you make to sample your LLM. See https://en.wikipedia.org/wiki/Arithmetic_coding)
Almost any temperature will work, as long as it is known to both sender and receiver. (The 'temperature' parameter can be used to change the distribution, but it's still effectively a probability distribution at the end. And that's all that's required.)
That being said, yes, some of my assumptions were incorrect, mainly regarding temperature. For practical reasons I was envisioning this being implemented with a third party LLM (i.e. OpenAI's,) but I didn't realize those could have their RNG seeded as well. There is the security/convenience tradeoff to consider, however, and simply setting the temperature to 0 is a lot easier to coordinate between sender and receiver than adding two arbitrary numbers for temperature and seed.
I misspoke, or at least left myself open to misinterpretation when I referred to the LLM's weights as a "secret key"; I didn't mean the weights themselves had to be kept under wraps, but rather I meant that either the weights had to be possessed by both parties (with the knowledge of which weights to use being the "secret") or they'd have to use a frozen version of a third party LLM, in which case the knowledge about which version to use would become the secret.
As for how I might take a first stab at this if I were to try implementing it myself, I might encode the message using a low base (let's say binary or ternary) and make the first most likely token a 0, the second a 1, and so on, and to offset the risk of producing pure nonsense I would perhaps skip tokens with too large a gulf between the probabilities for the 1st and 2nd most common tokens.
I was considering that, but I came to the conclusion that it would be an exceedingly poor choice.
Steganography is there to hide that a message has been sent at all. If you make it do double duty as a poor-man's encryption, you are going to have a bad time.
> As such, I approached it as a toy problem, and considered detection by savvy parties to be a feature, not a bug; I imagined something more like a pirate broadcast than a secure line, and intentionally ignored the presumption about the message being encrypted first.
That's an interesting toy problem. In that case, I would still suggest to compress the message, to reduce redundancy.
For the serious use cases you evidently have in mind, yes, it's folly to have it do double duty, but at the end of the day steganography is an obfuscation technique orthogonal to encryption, so the question of whether to use encryption or not is a nuanced one. Anyhow, I don't think it's fair to characterize this elaborate steganography tech as a poor-man's encryption — LLM tokens are expensive!
I guess it's a "rich fool's encryption".
Seed for the message above is 42 by the way.
(Just kidding!)
Their free service can also auto detect and notify you of leaked secrets, passwords or high entropy lines from your online repos.
I hope that more secrets adopt a GitHub like convention where they are prefaced with an identifier string so that you do not require heuristics to detect them.
----
Software entropy is a measure of the disorder or complexity of a software system. It is a natural tendency for software entropy to increase over time, as new features are added and the codebase becomes more complex.
High entropy in software development means that the code is difficult to understand, maintain, and extend. It is often characterized by:
Duplicated code: The same code or functionality is repeated in multiple places, which can make it difficult to find and fix bugs.
Complex logic: The code is difficult to follow and understand, which can make it difficult to add new features or fix bugs without introducing new ones.
Poor documentation: The code is not well-documented, which can make it difficult for new developers to understand and contribute to the codebase.
Technical debt: The code has been patched and modified over time without proper refactoring, which can lead to a tangled and cluttered codebase.
Low entropy in software development means that the code is well-organized, easy to understand, and maintain. It is often characterized by:
Well-designed architecture: The code is structured in a logical way, with clear separation of concerns.
Consistent coding style: The code follows a consistent coding style, which makes it easy to read and understand.
Comprehensive documentation: The code is well-documented, with clear explanations of the code's purpose and functionality.
Minimal technical debt: The code has been refactored regularly to remove technical debt, which makes it easy to add new features and fix bugs without introducing new ones.