Well the answers are at least interesting.

Although Physics.SE could have given an even better answer.

Well the post's text is actually "The post text however reads "At what distance can a face no longer be identified using a camera? At what distance can a figure of a person no longer be captured?"

oh

That's a lot more interesting, but what a low quality question.

indeed

It might have made sense from a spy satellite perspective.

I.e. to know what the best theoretical resolution is.

From what I know, current satellites are able to distinguish individual soda cans.

I don't think it can identify individual faces, though. Gait analysis would be possible from that distance, but those satellites are orbiting so it would be unable to record motion.

And I think geostationary satellites are too far away.

Just one little tweak like that makes it so much more interesting

How would satellite photos with that kind of resolution work? How many FPS could it get?

FPS wouldn't matter because it's moving so fast.

So how do you get the first picture? An algorithm to remove motion blur for however much exposure time you need?

If you wanted to stay in its field of view for more than a split second, you'd need to go many miles per second. The only satellites that stay directly above one spot are geostationary satellites which, as I mentioned, are way too far away to take good photos.

@FutureSecurity That's what I think.

Also, satellites in GEO are limited to only going around the equator. Spy satellites are LEO.

Looks like one pixel could be just a few centimeters. Not that I know enough to have any good idea of what it could actually be after such a brief search.

Well that's certainly correct to within an order of magnitude.

Geostationary orbits are limited to the equator, and geosynchronous orbits are too high to take photos.

Which leaves regular low earth orbit for keyhole satellites.

I don't think that the idea that the NSA is "x years ahead" is true for cryptography anymore. I wonder if there's some saying like that for other kinds of surveilance.

Yep, it used to be true but cryptography is now in the academic field.

All the NSA has is better funding for powerful computers (and even then, they aren't that far ahead). It just means they can do shit like find GNFS polynomials faster and get better collisions.

For surveillance on the other hand... they're not that far above some industry, but said industry is far beyond most commercial applications. That includes things like keyhole satellites.

So I'd say it's pretty similar to the difference between IC and academic cryptography, with the difference that academic cryptography is far more public than other areas of academia (e.g. fluid dynamics).

After all, not all the information required to build a nuke is online (although it's easy enough to get).

Meaning some covert group has really advanced fluid dynamics knowledge?

More like academics have better fluid dynamics knowledge than is public, and the NSA/CIA/etc shares that knowledge. It just means they can make better missiles and torpedoes.

But they aren't way, way ahead. Open academia could easily catch up if it wanted (read: was funded).

I recall reading about nuclear bomb design, and it was shown that a few PhDs in nuclear physics could discover how to build a working nuke from public information within a year or two.

The same is probably true for many other fields that only get funded by the government.

But really, the only thing the IC has is a lot of resources, and a lot of time. That's what makes them scary. Their exploits they have aren't that much different from any other high-end exploit kits out there. Their computing technology is not far ahead any other very well-funded custom design, etc. Their ability to parse and monitor data isn't much further ahead than public techniques. They just have a lot of implants. After all, XKeyScore is not much different from a customized Bro IDS.

I see.

Besides resources they also have different incentives. There might be scientific advancements that the commercial world just wouldn't bother pursuing because they can't extract enough value from it.

Exactly. DJB actually has some nice write-ups about incentives and corresponding threat models.

Cryptography academics want to find collisions in SHA-1 and attacks against reduced-round block ciphers. Perhaps the NSA cares far more about optimizing GNFS polynomial selection.

What DJB emphasizes is that we focus on making serial attacks harder, whereas the NSA and friends may very well be focusing on improving multi-target attacks, and that we should understand that.

One scary thing about the IC is that they don't need high accuracy. Maybe business wants to track everyone's movements through satellites. There's really only profit in it if they can track individuals for extended amounts of time. When it comes to bombing you can be more ham-handed, excuse civilian death, and still succeed in your mission.

Indeed. For them, knowing general trends might be enough OSINT to do what they want.

I don't remember where I read it, but I read something about the IC focusing very heavily on technology prediction. That is, using sociology and big data analysis with OSINT to predict what new or emerging technology will be adopted by their target. They can then get a head start attacking that technology.

E.g. in the early 2000s, they might have used that to predict that Tor would dwarf I2P and Freenet, and that they should focus more efforts on studying Tor before it got popular.

Or they'll try to determine if their target group (or groups) are more likely to adopt WhatsApp or Signal.

Android or iOS. Linux or Windows or MacOS, etc. OpenPGP or S/MIME. VeraCrypt or Bitlocker.

And that sort of thing doesn't require high accuracy. You don't need to know what each individual is doing and what they personally think and instead care only about general trends which can only be discovered from dragnet surveillance or heavy OSINT.

That would definitely be useful. I do suspect it's not as successful as the contractors make it seem. With so much overfunding they can just target a bunch of things and declare success on the path that does work out.

I dunno, I have a feeling that it's a pretty effective way to reduce costs and focus efforts.

Especially since it's not just about what tech individual groups will use, but what technology companies might start adopting. From that, insider knowledge is very powerful.

They might be able to predict whether or not Intel CET (forward edge CFI in hardware) will be the next big thing or whether it'll be forgotten like Intel MPX (high-overhead buffer overflow prevention).

And from that, they could determine what kind of mem corruption vulnerabilities they should collect.

Although I have a feeling that their focus is on much less well-known features, like different kinds of Spectre mitigations that are only available under strict NDA. But who knows? My contacts are dried up.

I see now. I was going to say that I saw the potential for cost reduction, but don't expect it to be pursued particularly seriously in practice.

The NSA is like Google (or rather, like Alphabet. Google is a subsidiary). They have a lot of different groups that are able to put 100% effort into a bunch of different techniques or ideas, just in case a few work.

I'm sure they have teams looking hard for preimages in SHA-2 and ciphertext-only attacks against AES, but those teams are likely far less well-funded and much smaller than those working on, say, optimizing ASICs for factoring 1024-bit primes, or analyzing data collected from taps.

I think I read that they pay contractors to analyze Freenet, whereas they work on Tor in-house.

:-/ Such a shame that we can't take that kind of funding out of military and policing and put it into things that benefit the rest of the world instead.

Indeed.

Imagine if even a fraction of the US defense budget (say, $400 billion a year) went to cancer research.

Speaking of having diverse teams, there was a bit of a hubbub when the Snowden leaks revealed that the NSA was working on "Tau statistics" (the Kendall rank correlation coefficient) as a way to break AES. People connected that with their "vast new cryptanalytic capabilities that are coming online" and panicked. The truth is that whoever was working on Tau statistics was likely a very small team just doing a little research and writing a paper no more relevant to real cryptanalysis than XSL is.

Their "vast new capabilities" turned out to be likely nothing more than breaking 1024-bit DH groups.

I remember that. "Tau statistic" sounded about as ominous as you could make some kind of "statistic". I looked into it and it definitely seemed like it was completely irrelevant.

Indeed. If it was actually a promising way to break AES in a practical setting, it would likely be classified at a high enough level that it would not have been available to Snowden.

Hell, they didn't even use a codeword for it! That's how you can tell it was not a promising attack. ;)

The academic world is a lot better at gauging what kind of successful cracks the NSA likely has than people give it credit for. The DH thing was predicted... people were making noise about it I think. Same for Dual EC DRBG. People were also making noise about RC4, SHA-1, MD5, OpenSSL...

Yeah the WeakDH paper gave very compelling evidence that it was what the NSA was using.

The same sort of people that dismiss warnings as conspiracy theory or "impractical" also tend to get upset when they're supposedly blind sided.

And since academia is not that far behind the IC (if it is behind at all), they can absolutely guess where the next break is going to be. The NSA may be working on a better chosen-prefix collision attack against SHA-1 than we care about (since all we care about is analyzing SHA-2 and SHA-3, and largely forgetting about SHA-1), but certainly not some magical way to break full-round AES.

After all, they managed to find a chosen-prefix collision against MD5 independently.

@FutureSecurity Reminds me of valerieaurora.org/hash.html. Particularly, the section titled "Reactions to stages in the life cycle of cryptographic hash functions". I'm sure you've seen this. :P

I remember seeing that, but the last time I looked was probably long before "[3] Google spent 6500 CPU years and 110 GPU years to convince everyone we need to stop using SHA-1 for security critical applications. Also because it was cool."

"Programmer reaction" seems to be a bit optimistic

That's what I thought as well. I mentally replace it with "competent programmer reaction".

Why is SHA-2 considered to have "minor weaknesses"? Just because of the SHA-3 competition?

E.g. "Used by a particularly adventurous developers for specific purposes" for primitives under peer review, as in the case of Gimli being used by the developers of libhydrogen.

@FutureSecurity Huh. Yeah that doesn't really make sense. Maybe length extension attacks?

But if that was the case, the entire lifetime of SHA-2 would be labeled yellow.

On Corrective Patterns for the SHA-2 Family

> When accounting for the complexity of 2^9 per corrective pattern, the previous analysis of the message schedule yields lower bounds on the complexities 2^27 for SHA-224/256 and 2^45 for SHA-224/256. These complexities are significantly less than the 2^n bound. It is no longer certain that SHA-2 resists this attack. More detailed analysis of the message schedule is required.

I guess this counts. It's certainly a very minor weakness though.

I don't yet understand what that part means.

This is if the register state is known, so I imagine it'd be relevant to side-channel attacks.

Although I'd be unlikely to call that a "minor weakness" at all, now that I think about it.

That's the only thing on eprint which uses the words "corrective patterns".

> However we show that slightly simplified versions of the hash functions are surprisingly weak : whenever symmetric constants and initialization values are used throughout the computations, and modular additions are replaced by exclusive or operations, symmetric messages hash to symmetric digests. Therefore the complexity of collision search on these modified hash functions potentially becomes as low as one wishes.

From the abstract of one of references cited. lol

researchgate.net/publication/…

heh

Random question...

How difficult would a second preimage attack against an n-bit hash function be if the attacker is free to change any bit in the message and digest from 1 to 0, but not the other way around?

It feels like the answer should be so obvious that I don't want to post it on the main site.

Medical garbage has been making my brain slow down. That's not something I've ever looked into, so I have no idea.

ah

I guess I'll ask it on the main site then.

Dear America. You lose some very productive workers with your broken healthcare system. It's irrational. It's counterproductive to the economy. Do better.

That SHA-2 thing looks like bullshit. It's harder for me to tell now though because reading comprehension is down.

It seems like bullshit to me as well now. I would contact the author but... I'm lazy.

That second paper... Change the IV values, change round constants, and remove of major portion of the non-linearity???

In MathJax, what specifies length? Is it |m| to mean the length of m?

That notation is what I use. Not sure about what the proper MathJax is though. I think it just works with plain old '|'s.

(deleting post while I edit it a bit)

Putting bars around m does mean "the length of string m" in computer science when dealing with languages/grammar. It's measured in the number of symbols, not bits or bytes. But in cryptography stuff it's usually implied that the alphabet is the set {0, 1} so it always means length in bits.

I worded it using English just in case.

Speaking of symbols and alphabets, do you understand what's up with Paul's use of "bits per bit"? I think Shannon did use terms like that.... but it's used in the context of communication channels. There isn't much use for it in cryptography though.

Does it sound as absurd to you as it does to me?

Bits of entropy per bit of random output.

The term is pretty much only used by crappy randomness estimators.

You mean toys like ent?

Yeah, or dieharder, or haveged's internal entropy estimator.

It's usually measured in bits per byte though, not bits per bit.

So an ideal random source is 8 bits/byte, but a realistic one might be, say, 6.295103 bits/byte.

It sounds dumber when it's phrased bits per bit. But it sounds bad to me either way.

Unless Paul is talking about measuring raw noise sources, he's using the term wrong.

It's not even used then. Instead of "bits per byte" you'd use "bits per sample".

Sure, but bits per byte is just the term that a few programs use.

It's not an academic term.

I dislike the weight the term carries. It definitely supports the misconception that entropy is something that can be moved around, diluted, or depleted as if it were something substantial...

... it also bugs me science brain. Both "bits per bit" and "bits per byte" would be a unitless value.

You'd never hear a chemist say "liters per liter". Either they would drop the unit or say "liters of x per liters of y".

Yup

I feel like the idea of entropy as being analagous to a substance is probably the biggest source of confusion for people on the web. It's hard to teach humans to think of in terms of pure math once some other mental image has taken hold long enough. (I'm not talking about Paul specifically... But it is too bad that the way StackExchange calculates and displays reputation makes him seem like a more credible source.)

Uh shit, I'm having a major brainfart (very tired today). What's the term for the weight of symbols in a set, where a blank of 0.5 would mean there's an equal number of each symbol (for {0,1} it would be 50% 0 and 50% 1)? It's common in coding theory and compression. What is blank that I forget?

Hamming weight describes the total number. Let me think about the % part

Hamming weight that was it.

I misremembered the definition.

@FutureSecurity It's a common misconception. That's why people worry about it "running out".

"Mean [bit value] of 0.5"... is probably why I couldn't think of any term. Not important enough to earn a specific term, maybe? I was somewhat surprised to see that "Hamming density" wasn't in use... because wordplay

Yeah it was me misremembering it because insomnia.

> The variables in this case are the length of the message, the hamming weight of the message, and the size of the digest (assumed to have a hamming weight half that of its length in bits, on average).

I just added that to my question.

It's turning out to be harder for me to calculate than I had expected.

I can come up with an upper bound quite trivially (after all, a hash with all zeros in that scenario would result in the possibility of a second preimage attack with a complexity of 0). I can lower it slightly by taking into account the probability that all but one bit is 0, all but two, etc., but then combining that with a generic second preimage by modifying the message is making it harder.

Giving the attacker an advantage when dealing with the digest (creating equivalent hashes), and a disadvantage when dealing with the message (fixed length and less freedom in changing bits) is not something I see commonly looked at, probably because it only applies to a specific scenario.

Is the question that's currently up the same one you want answered? I think you can ignore the part about changing message bits. For a sufficiently long message you'd have enough zeros in the message to generate enough new m' values

Entropy "paradoxes" that people come up with are pretty common to. For example use a 256 bit hash function to hash 128 bits of entropy, then take the first 128-bits of that digest. Well that must have 64 bits entropy because taking the last 128-bits must be no different!

@FutureSecurity For a long message, you're right that the effect would be negligible.

I can't make that assumption, though.

This is particularly important because the message is a mix of data and code, so it can't be changed arbitrarily. In addition to only being able to change 1 bits, there's only a finite number of bits that are worth changing. So I guess its hamming weight define the maximum.

Sounds like it's one of those puzzles that stay hard to figure until (at least) after you formalize the rules you want to impose on yourself.

Oh. I think I know what you meant now.

In my question, I don't have to specify the fact that not all 1s are open to me changing them. Instead I can define the hamming distance of the message as whatever I want (up to the size of the message in bits). It's the "effective" hamming distance rather than the actual hamming distance. For the purpose of the question, it doesn't matter. A 0 bit and a 1 bit that I can't change without breaking something (as well as 1 bits I must change) are equivalent for the purpose of the question.

That's the reason I can't assume that a big enough message will be malleable enough that I don't need to take it into account. There may very well be only a few bits that are already 1 bits and which don't change the behavior of the firmware at all (e.g. changing one nop into another kind of nop).

If I'm able to come up with an equation to plug those variables in (digest length, message length, "effective" message hamming weight), then I can decide whether or not it's feasible to do what I want.

I've got a pretty beefy hash-cracking rig, but a few bits is the difference between practical and not.

oops, s/distance/weight/g

Would it suffice to come up with a probability of success as a function of the number of digest bits, the number of zeros in the original digest, and the number of message/digest pairs?

Yes, although it would also work if the function calculated the complexity of the attack. That way one variable can be omitted (the number of message/digest pairs). But it works either way.

Er, the function also needs to include the number of one bits in the message.

g2g

@MaartenBodewes Regarding your comment, I've described a bit more about what I've tried here. Also, you have no idea how badly I wanted to reply "I've tried nothing and I'm all out of ideas". :P

@forest are you trying to perform fault attack?

@kelalaka There are several kinds of non-volatile read only memory hardware. At least one kind is semi-read-only. It ships with every bit initially set to 1. You can set any bit to zero, but once you do it's irreversible.

Normally you only program the ROM once. But there isn't something to stop you from making changes as long as those changes require zeroing bits, no zero -> one flip is possible. (And from the perspective of software it is ROM. The microcontroller isn't wired to allow software to zero out a bit.)

I suppose forest's ROM contains code followed by a hash of that code. It's used to check the integrity of the firmware, but it's not truly read only.

Had they instead encoded digest bits as a sequence of two ROM bits then you could get actual integrity out of the ROM. Write 01 if a digest bit is zero. Write 10 if the digest bit is one. Then the ROM hacker can either leave a pair of bits as-is or make them both zero... If you see 00 then you know there has probably been tampering.

It's electronics that's sort of analogous to punch cards. You could punch a hole in the paper, but once you do there is no way to undo clearing the bit.

That's exactly right.