Is there a contingency plan in the event of a catastrophic attack on AES? NIST selected Rijndael in 2000 to be AES. In a paper from the Serpent authors, they mention that there was the possibility of choosing a second cipher as a backup in the case of any severe breaks:

  I believe that there should be only one standard. NIST should decide on one standard in order to ensure that the standard is accepted and adopted as soon as possible. However, NIST can publish the choice of a backup cipher which will replace the standard in case it is broken or in case other circumstances (such as intellectual property problems) will prevent it from being used by the public.

NIST has not done this, according to section 2.4 of a report from NIST. Is there any process in place in the event that a severe cryptanalytic attack against AES is discovered? Imagine it's 2029 and a new paper comes out showing that all 14 rounds can be broken with a complexity of $2^{50}$ and a negligible amount of known plaintext. Would there be any official steps taken by NIST, for example changing the standard to use more rounds? Would one of the other AES candidates be chosen as AES2?

I don't believe that there will be a major break in the cipher without prior cryptanalysis showing it to be gradually weaker and weaker, so I highly doubt the total break, if one is ever discovered, will come as a surprise. However, I am still curious to know if there is an official policy on the matter.

I'm not aware of any official NIST policy on the matter, so I can only make educated guesses.

I guess new algorithms have sprung up and are already in place. ChaCha20 is used in TLS 1.2 and 1.3. For hash functions, neither SHA-2 nor SHA-3 are depending on AES in any way. The sponge function in Keccak (SHA-3) can also be used as a symmetric cipher (Ketje, Keyak and Kravatte) and - with a bit of tweaking - as MAC (KMAC). So rather than to move backwards I think NIST would simply standardize on existing ciphers together with more modern ciphers based on Keccak.

Although I see merit in the answer of AleksanderRas, I personally don't think that one of the original AES candidates would be chosen as new AES (or FES, for fixed encryption standard). The world has moved on; there are likely more secure and certainly faster block ciphers around. For instance, I could see that Bruce Schneier and the Skein team would choose Threefish over Twofish. Possibly Serpent would make a chance if Rijndael is broken, as runner up with a high security margin. It does seem to have much in common with AES though, so maybe a break could also influence the security of Serpent, even if it does have a high number of rounds.

This brings us to an important final point: possibly a broken AES could simply be fixed by upping the number of rounds. In that case: the king is dead, long live the king. The hardware is there after all, and quite often the number of rounds can be configured. This would make the most sense in the short term and would allow NIST some breathing space to think of a replacement.


Is it possible to decrypt cryptowall-encrypted files? I am writing regarding a certain ransomware program called cryptowall (prop 4.0).
I have lost many documents to this, and as it so happens, I have a few file duplicates before and after they were forcefully encrypted.

My question is whether or not it is possible for someone knowledgeable to figure out the key used and decrypt these particular files by comparing the two copies?
Thanks for taking the time to even read this; you can't imagine how important these documents are to me, pretty much 8 years of work.

Cryptowall (from about version 3 and onward) uses AES encryption. The kind of attack you are describing to recover the key(s) used is a known-plaintext attack. Even with an absurd amount of plaintext-ciphertext pairs, there are no known reasonable attacks on AES in the foreseeable future. The AES key itself is encrypted with RSA, but the known plaintexts aren't relevant, as the RSA key is not used to encrypt your files directly.

If you can't live without the documents, your only real option is to pay the ransom. The only other option is to live without your files, and hope that in the future the perpetrator is arrested and the keys are released.

And of course, be sure to keep your antivirus software up-to-date and follow other good practices in the future.


How does the CBC Padding Oracle Attack work in General? Right now we don't have a single generalized question asking how the CBC padding oracle attack works. We have e.g. this one and this one but the former is distracted by the concrete values being thrown around and the specific problem the poster has and the latter is distracted by the complications introduced by ASP.NET.

So (representatively) my question is:
How does the standard CBC padding oracle attack work?

Optional extensions which may be interesting here: What if the padding oracle checks the (untamperable) ciphertext length before checking padding?

First before we can get into the details of the attack, we need an intuition why it works. There's a nice picture hosted on the TLSeminar page illustrating this point:

which basically says that we want to modify the last byte $\color{red}\times$ of the second-to-last block so that the CBC decryption of the last block which has "$\color{blue}?$" as its content yields $\color{green}{\mathtt{0x01}}$ instead. This of course works because CBC decrypts as $\color{green}{M_i}={\color{blue}{D_K(C_i)}}\oplus \color{red}{C_{i-1}}$. Finding the right $\color{red}\times$ is achieved by querying all 256 values to the padding oracle to which you should only get one positive response (when you hit the correct plaintext guess or accidently hit a longer padding).

So now that we know roughly what to do: Namely guess the last yet unknown byte until you get confirmation, let's get into the details.

Let $i$ by the current plaintext octet counted from the end that we are trying to recover, including padding. Initially, let $i=1$. Further let $G_i$ be the set of potential plaintext octets recovered in iteration $i$.
Let $c_{k-1}$ be the second to last ciphertext block or if $k=1$ then it corresponds to the IV. Define $c'_{k-1}:= c_{k-1}\oplus (0^{n-8(i-1)}\|g_{i-1}\|\ldots\|g_1)\oplus (0^{n-8i}\|\texttt{i}^{i})$ where $\texttt{i}^i$ is $\texttt{i}$ encoded as one octet repeated $i$ times and the $g_i$ are elements of their respective sets $G_i$ which we currently use.
For all $g\in\{0,1\}^8$, query the oracle with $c'=c''_{k-1}\|c_k$ where $c''_{k-1}:=c'_{k-1}\oplus (0^{n-8i}\|g_i\|0^{8(i-1)})$, add all $g_i$ for which $P(c''_{k-1})=1$ to $G_i$.
If $G_i$ contains $0$ or $256$ entries, that is the oracle always responded positive or negative, find the largest $j<i$ for which $G_j$ has more than one entry.
Remove $g_j$ from $G_j$ and set any other element of $G_j$ to be $g_j$.
Note that $j$ may be negative here which then implies that a previously "discarded" ciphertext block needs to be re-added and $j$ be incremented by $n/8$.
This addition of old blocks needs to be repeated until $j$ is positive again.
If $G_i$ fulfilled that special condition, set $i\gets j+1$ otherwise update $i\gets i+1$ and pick any element of $G_i$ as current $g_i$.
If $8i>n$ set $i\gets 0, k\gets k-1$ discard the last block and return $g_{n/8}\|\ldots\|g_1$ as its contents.
Go back to 1.

As this is quite the wall of text, here's an UML sequence diagram illustrating the above procedure for the case that the $G_i$ always have size 1:

The idea of the addition of these sets is that indeed we may get unlucky and hit a second-to-last byte of $\texttt{0x02}$ which results in $\texttt{0x02}$ and $\texttt{0x01}$ being accepted by the padding oracle. So instead we take a guess which plaintext guess was right and go back to take another option if needed later, e.g. if we obviously did a bad guess previously due to now always satisfying the oracle.

If the padding oracle enforces a given ciphertext length, we can still recover data, but if the padding is only allowed for up to one block, we can only recover one block or else we can recover at most $255$ bytes if arbitrary length multi-block padding is allowed. For this then we simply don't discard the ciphertext blocks and keep incrementing our $i$ beyond $n/8.$


Why does Neumann think cryptography isn't the solution? What did Peter G. Neumann mean by:

  If you think cryptography is the answer to your problem, then you don't know what your problem is.

(eg: quoted in the New York Times, February 20 2001)

That New York Times article actually continues after that quote:

Dr. Neumann explained that there are always ways to get around cryptography barriers and that these methods have nothing to do with breaking codes.
"It's like the voting machines," he said. "You'd like to have some integrity in the electoral process and now folks are coming out of the woodwork saying, `We have this perfect algorithm for privacy and security.' "

So it's very clear that this is the difference between secure systems and just the cryptographic algorithms.
That said, if things are managed right then cryptography certainly has its benefits.

As another example, nobody will argue that TLS doesn't have its advantages. But even there, the huge number of Certificate Authorities and the enormous amount of trust put on them and the browser manufacturers threatens the system, even though the TLS protocol is relatively secure when implemented correctly.


Is it possible to obtain AES-128 key from a known ciphertext-plaintext-iv tuple used the encrypt the plaintext? i have a file, which was encrypted with AES-128 in CBC mode. I know the content of original file and know the iv used to encrypt that file.So, just wondering if it's possible to recover the key used from the information provided.

Ciphers are designed to withstand far more adverse situations than the single known plaintext/ciphertext pair that you describe.  In particular, they are intended to be secure against chosen plaintext attacks, where:

The attacker submits plaintexts of their choice and are shown the resulting ciphertexts, as many times as they like;
The attacker's goal isn't to recover the key, but just telling the cipher apart from random results, which is much easier.

There are no known practical chosen plaintext attacks against AES, and there are security proofs for CBC mode.

There are of course impractical attacks that work only in theory.  You could just attempt $2^n$ distinct keys and you have a $1/2^n$ chance of finding the right one.  But that means that you need $2^{127}$ attempts—about $1.7 \times 10^{38}$, an astronomically large number—to have a 50% chance of success.


Are there any (asymmetric) cryptographic primitives not relying on arithmetic over prime fields and/or finite fields? Trying to figure out if any (asymmetric) cryptographic primitives exists, which do not rely on arithmetic over a prime field and/or arithmetic over a finite field, some people might get lost in research. Therefore, here’s the related question (inspired by this comment):

Does any asymmetric cryptographic primitive exist, that doesn’t rely on arithmetic over prime fields and/or finite fields?

If, which one(s) would that be?
If not, it would be nice if you would also explain why not?

Braid cryptography?  Knapsack cryptosystems, like Nasako–Murikami?

Lattice-based cryptography tends to work in polynomial rings or modules with coefficients in finite fields, but whose higher-level structure is not a field.

Also: don't forget RSA!  RSA works in a ring, not a field.


Non interactive zero knowledge proof with common reference string I would like to have some explanations about Non Interactive Zero Knowledge Proof. I saw with an example how to use the Fiat-Shamir transformation on Schnorr identification scheme to get a NIZK and I understood how it works in the random oracle model.
What I don't understand is how does a NIKZ work in the common reference string model (CRS). If I understand it right, the principe is that the CRS is generated in a trusted way and is used by the prover and the verifier to establish the truth of a statement.
Without worrying about the generation of this CRS, I would like to know how an algorithm works with a concrete example. I found lots of examples in the random oracle model but I didn't find any with a CRS. Can someone explain to me or give me some links that illustrate this concept in a more practical way, for example with a demo implemented in some language or from a library ?

A NIZK in the CRS model consists of algorithms $(\operatorname{Setup}, \operatorname{Prove}, \operatorname{Verify})$ where
$$\operatorname{Setup}(1^\lambda)\rightarrow (\sigma, \tau)$$
generates a public CRS $\sigma$ and a verification state $\tau$. The proving algorithm $$\operatorname{Prove}(\sigma, x, w)\rightarrow \pi$$ uses the CRS, a statement and a witness to produce a proof $\pi$, which the verifier can check using the verification state
$$\operatorname{Verify}(\tau, x, \pi) \rightarrow 0/1.$$

Such NIZK systems exist for virtually any statement you could be interested in, namely for any $\textbf{NP}$ relation. You can find an implementation of a NIZK for Boolean circuit satisfiability here: https://github.com/scipr-lab/libsnark


How to publish a cipher (concept)? In the last months I was searching for a subject for my bachelor thesis. I came up with an idea for a new cipher concept that works by combining already known techniques in a (hopefully) new way.

So I talked to our professor for cryptography. Although she could not find any obvious weaknesses she mentioned that the review of a cipher is an ongoing and protracted process and therefore not suited as a subject for a bachelor thesis.

Is there a way to publish the concept to get some reviews?
What could one do to prevent the idea from falling into oblivion somewhere on my hard drive?

Update

I totally understood her reasons why this subject is not suitable. The question was more about the possible ways I could evolve, publish or analyze the idea (independently from my thesis). Sorry for the confusion this might have caused.

First : Welcome to Crypto.SE.

Even though you are quite young, it should not be a reason for someone to stop you : Alan Turing was 23 (still undergraduate) when he undermined the work of Alonzo Church (on untyped $\lambda$-Calculus). I'm not saying you should always provide your idea, but if you can defend them, have fun.

About your cipher : The first thing you should do, is to analyze your own cipher (Differential Cryptanalysis... Linear Cryptanalysis...) An overkill approach would be in the same way that Joan Daemen and Vincent Rijmen did for Rijndael. If you submit a cipher, one would expect at least a formal analysis of why you think this is a good idea. One is unlikely to spend time to review your work if you did not prove your part at the beginning. However, the same principle apply as writing clever code :

  Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.
  - Brian Kernighan

If you can't break a block cipher, it doesn't mean that other won't.

Some hint about how to start :
- How do you test the security of your cipher?
- How do I test my encryption? (absolute amateur)

Most ciphers are published (or at least get known) in competitions such as :

AES in 1997,
CRYPTREC,
NESSIE,
or at the moment CAESAR (Authenticated Encryption).

And if you think your idea is really great, you can also try to submit it as a paper to a workshop, Journal or conference. Here are some examples (and accepted) submissions that you probably never heard of :

SQUARE
SHARK

Good Luck !


How are boolean functions used in cryptography? I recently started becoming interested in Boolean functions. Because they are defined as $f: \{0, 1\}^n \rightarrow \{0, 1\}$, or in other words only over $\{0, 1\}$, I guessed they can somehow be applied in cryptography. After all in cryptography (in some sense) we have an input which can be defined as bits, and then we do some kind of operations on those bits to scramble them.

Additionally, many algorithms (like BLAKE, ChaCha20, etc.) use the ARX (addition-rotation-xor) method. And as long as I know some parts of AES does the same. I have already read that Boolean functions are important for the design of S-boxes, but I want to learn how more they are applied in cryptography.

So, how and where (hash functions, block ciphers, stream ciphers, public key cryptosystems, etc.) are the Boolean functions used in cryptography (either for designing algorithms or cryptanalysis)? Can they be used in some more complex algorithms that are based on things like finite field arithmetic, elliptic curves, lattices, etc?

Many properties of boolean functions are used in stream and block cipher design, e.g., when they are used as filtering and combining functions. Some important examples are:

Nonlinearity (minimal Hamming distance of the truth table of the boolean function from affine functions), must be high for resisting linear/affine approximation attacks.
Correlation Immunity (CI) and resilience (CI is the maximal nonzero weight for which all Walsh-Hadamard transform coefficients are nonzero, and quantifies resistance to divide and conquer style correlation attacks; resilience is CI plus balancedness). There is a tradeoff between CI and algebraic degree of the boolean function $f$, namely $deg(f)+CI\leq n-1$, for an $n$ variable boolean function, discovered by Xiao and Massey.
There are links between the weight of the complex DFT and linear complexity of sequences (and all sequences can be expressed as Boolean functions after a choice of basis of $GF(2^n)$ over $GF(2)$ and appending zero) called Blahut's theorem.
There is a fantastic recent book on applications of boolean functions in cryptography, "Cryptographic Boolean Functions and Applications" by Stanica and Cusick. Older relevant books include "Analysis and Design of Stream Ciphers" by Rueppel and "Stability Theory of Stream Ciphers" by Ding, Shan, and Xiao. Any issue of Designs, Codes and Cryptography, and quite a few Crypto conferences will regularly have papers on these topics. See the IACR eprint server as well.

Finally, Sboxes are just vectorial (vector output) boolean functions, see the chapter entitled Propagation and Correlation in the AES Proposal, a version of which also appears in the book "The Design of Rijndael" by Rijndael designers Daemen and Rijmen.


Why Camellia has 4 Sbox I asked a question about using 16 different Sboxes in AES each for one state byte instead of using same One Sbox for substituting 16 state bytes (See the Question Increase in AES SBox). The answers i got are like given below

  at least one disadvantage of using 16 S-box to change the 16 bytes. The size of the code and the look up tables (should you use such implementation) would increase the size of the code. This increases the surface of exposure for cache timing attacks.

Now i wonder, why Cameillia designers used 4 Sboxes with almost similar properties? What is the main advantage of using more than one? Even Twofish uses 4 key dependent Sboxes.

The only way you will have a certain answer will be by mailing their designers.

Using multiple S-boxes increases the size of the code and decreases the possibility of working with different blocs in parallel.

Using a single S-box also simplify the way the specifications have to be written. The simpler the specifications are, the less prone to make error at the implementation step you are.

Not related to Camellia but on the same idea:

  JP Aumasson: why nobody uses SHA-3? FIPS 202, a 29-page specs written for cryptographers, not for users [source]

  JP Aumasson: seriously NIST, in 2.5 years no one had the idea that, perhaps, it would be good to simplify that thing? like, ditch the greek part [source]

However, using a single S-box implies some sort of symmetry in your bloc cipher which MIGHT be the reason why the designers of Camellia preferred to use 4 S-boxes instead of only one.


A secure public-key cryptosystem Is there any public-key cryptosystem that is (possibly) secure against $NP\cap coNP$ adversary?

Is there any public-key cryptosystem that is (possibly) secure against $NP\cap coNP$ adversary?

Hash based signatures come to mind; essentially, to break them, you need to find a (second) preimage of the underlying hash function, and that problem is not known to be within $NP\cap coNP$.
Of course, the current instantiations are based on fixed-sized hash functions (and hence are not within $NP$); however generalizing the concept to variable length hash functions should be fairly straight-forward.


Can a large file be hashed down to 32 bytes, and then reconstructed from the hash? We can hash a file or data using multihash or SHA-256, but can we retrieve the original data or file from the hash?

Are there any methods to retrieve the original file or data from a hash of it without using IPFS?

Or is there any encryption method which encrypts a 5 MB file and outputs a hash-like content of 32 bytes so that we can retrieve the original file from that 32 byte content?

No, there is no way to compress (or hash or encrypt or whatever) a 5 MB file into a 32 byte hash and then reconstruct the original file just from the hash alone.

This is simply because there are many more possible 5 MB files than there are 32 byte hashes.  This means that, whatever hashing or compression or other algorithm you use, it must map many different 5 MB files to the same 32 byte hash.  And that means that, given only the 32 byte hash, there is no way you can possibly tell which of those different 5 MB files it was created from.

In fact, the same thing happens already if you hash 33 byte files into 32 byte hashes, and then try to reconstruct the original files from the hashes.  Since there are 256 times as many 33 byte files as there are 32 byte hashes, that already means that there must be several different files that have the same hash.  With 5 MB files, it's many, many, many times worse yet.

So how can something like IPFS work, then?

Basically, it relies on the fact that even the number of possible 32 byte hashes is really huge* — much, much larger than the total number of actual files (of any length) that humans have ever created, or are ever likely to create.  So, while we know that there must be many possible files that have the same 32 byte hash, the chance of actually finding two different files that just happen to have the same hash by chance is still so incredibly small that we can basically assume it will never happen.

(Also, cryptographic hash functions like SHA-256 are designed so that, hopefully, there are no practical ways to deliberately find files with the same hash more efficiently than by just hashing lots of files and hoping against all odds for a random collision.)

This means that if we have some kind of a (possibly distributed) database containing a bunch of files and their SHA-256 hashes, then we can be pretty sure that it will never actually contain two files with the same hash, even if that's theoretically possible.

Thus, as long as we have access to such a database, we can use the hash of any file in the database to look it up, and be almost 100% certain that we will only get one matching file back, not two or more.  Technically, the probability of getting multiple matches is not quite exactly zero, but it's so incredibly small that it can be safely neglected in practice.

*) In fact, it's 28×32 = 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936.


Why use symmetric encryption with Public Key? A. From what I heard (and I am beginner at a security/cryptography), if you have a payload that is very large, asymmetric is a no-go.

B. Also, if you do have secret symmetric (e.g. AES) keys, you might not want to share them with others, if they have high importance to you.

I am trying to understand things and I cannot find good enough internet resources explaining this use case.

Here is the reasons I have thought of, for doing such an encryption:

asymmetric encryption is not available; e.g. due to large data size
symmetric keys are available but you do not want them to be shared with other parties
sender/encryptor needs to send data to the receiver securely (encrypted)

Please validate/criticise my ideas or add others.

I think you're looking for Hybrid cryptosystems.

As you correctly noted it's not only unsafe to encrypt large data with a asymmetric system it's also very slow compared to symmetric systems. That's why we usually use both of these systems together (hence hybrid) to "fill each other's gaps".

We share a symmetric key using asymmetric cryptography. The advantage is that we only have to share the symmetric key once at the beginning of a session and all succeeding messages will be encrypted using the symmetric key. The asymmetric system provides safe key-sharing and the symmetric system guarantees fast encryption / decryption.

  B. Also, if you do have secret symmetric (e.g. AES) keys, you might not want to share them with others, if they have high importance to you.

That's true, but we always create new keys for each communication channel, we don't use a single symmetric key for all communication.


Lamport signature: How many signatures are needed to forge a signature? Lamport signature: Signing the message Note that now Alice's private key is used and should never be used again. The other 256 random numbers that she did not use for the signature she must never publish or use. Preferably she should delete them; otherwise, others gaining access to them would later be able to create false signatures.

If Lamport's signature scheme would be used incorrectly, say you would use it more than once. How many signatures of distinct messages would you need to forge a signature?

I'm thinking if you have one signature and then the "opposite" message (not really message but the message's hash sum) so every 0 in the first message is a 1 and 1 is 0. If you had those two signatures you would have everything you needed from Alice's private key.

But that's probably not realistic to think that you get exactly those two messages. Is there some general formula for how many signatures you would need?

Thanks!

If the message is random each additional signature halves the security level. If the message is chosen by the attacker, two signatures (of messages where each bit differs) are enough for a complete break.

A security level of about 64 bits can be broken by a determined attacker, and a level of 32 bits can be trivially broken on a single home computer.

So if you use 256 pairs, which is a reasonable level, since it offers 256 bit security against second-preimage attacks, and 128 bits against collisions, practical attacks are possible once you use the same key three times, and it's trivial to find messages-signature pairs once you use it four times.

Note that at this point the attacker can't fully determine the message he wants to sign, he needs to try $2^{64}$ (after three sigs) or $2^{32}$ (after four sigs) different messages to find one that he can sign. This usually isn't a problem for the attacker, since many things he might want to sign have parts the attacker can choose freely.

Why does it halve after every signature?

When you observe a single signature, you know one hash from each pair. So to create a signature you need to have a message hash that matches every single bit of the signature.

When you observe two signatures, you know both hashes from half of the pairs, and only one hash from the other half. So the message hash only needs to match the half where you only know one.

When you observe three signatures, you know both hashes from 3/4 of the pairs, and only one hash from the remaining 1/4. Now you only need to match 1/4th of the original bits.

etc.


estimating entropy/randomness as fail-safe mechanism Real-world encryption systems are often not broken algorithmically but because the implementation has a bug. Sometimes the bug only happens in circumstances that could not have been foreseen, such as weak random numbers, or an error in a library causing e.g. predictable IVs.

So I wonder, are there workable methods of estimating randomness or entropy that could be helpful to detect (a subset of) actual failures in cryptographic systems?

As a simple example, such an estimator could be fed with consecutive CTR IVs and alert higher protocol layers when there is an apparent failure, because all IVs are identical for example. Or an estimator could be fed with encrypted DES output to detect a bug in the implemention.

Such practices are commonly applied to results of some random number generators, but less often to other applications.

There is one very common such fail-safe test

NIST's FIPS 140-2 requires very simple contiguous test for random number generation: store previous generated block and compare. Only if the block is different it is assumed that the RNG did not fail.

From FIPS 140-2 4.9.2:

  Continuous random number generator test. If a cryptographic module employs Approved or non- Approved RNGs in an Approved mode of operation, the module shall perform the following continuous random number generator test on each RNG that tests for failure to a constant value.

More entropy tests

The standard (FIPS 140-2) used to require more tests (mono bit test, poker test, runs test, long runs test). These tests give fairly good estimate of if input appears random. These were decommissioned, because they work better with NDRBG than RNGs required by the standard (see FIPS 140-2 Annex C if you need details), and because for some cases it is excessive requirement to produce 20000 bits for analysis (it may be that you just needed one 128-bit key). AIS31 standard used to evaluate true random number generators uses some very similar tests.

Used in practice

These tests are useful against some hardware random bit generators and for this reason, Linux rngd program is running the tests (previously part of FIPS 140-2) to ensure quality of entropy gotten (for example from /dev/hwrng) and to ignore inputs which appear non-random.

You may use Linux rngtest program to apply these tests to data of your choice, for instance, examine output of (possibly) buggy encryption software.


How does a backdoor in the RNG enable an attacker to break encryption protocols? I'm wondering how a backdoor in a random-number generator (as rumored the NSA have placed), actually compromises the security of things like VPNs or TSL/SSL.

What I understand is that, if such a backdoor exists, then after observing a certain number of pseudorandom bits, the attacker can then predict the rest of the pseudorandom sequence.

Can someone walk through the steps of how this allows an attacker to actually read encrypted packets?  For example, how would an attacker get access to the first N random bits of a pseudo-randomly generated key in the first place.  Is the problem that any random key is effectively only N bits long because if an attacker guesses the first N correctly, he can generate the rest of the key using the backdoor?  Or is it something more complicated.

There are three ways a RNG can fail

Insufficient randomness in the input
Losing randomness as a result of the random transformation
Leaking bits through an intentional or unintentional side channel

Each fail weakens things. A backdoor in a random number generator is like actively implementing such a fail, introducing possible ways to lower the security of the random number generator since it becomes less random.

It it's not as if a backdoor in a random number generator always directly breaks things like SSL, but they can have the ability to. The real problem is that a well constructed backdoor is near to undetectable, while allowing an attacker to take security shortcuts that wouldn't be available normally. And that would happen without the person using the RNG for security purposes noticing the backdoor.

Imagine using such a backdoor to seed something... it would look perfectly random to you, but the one who implemented the backdoor might be able to recover the whole state of the RNG by just looking at - let's say - 32 bits. That would mean you're in big-big trouble. Now imagine you feel good, safe and secure because you aren't aware of a backdoor lurking behind the screens... get a creepy feeling? Good!

Practically describing it all would be too broad, and giving you a walk-trough would be too long and too technically detailed... but if you want to learn a bit more generally why a backdoor in an RNG might be a real security issue, you could read a bit about it in "The Many Flaws of Dual_EC_DRBG " which talks about a prominent, recent backdoor in an RNG and shows what practical impacts it would have had on cryptographic implementations:

  If I use the Dual-EC PRG to generate the "Client Random" nonce transmitted in the beginning of an SSL connection, then the NSA will be able to predict the "Pre-Master" secret that I'm going to generate during the RSA handshake. Given this information the connection is now a cleartext read. This is not good.


Crypto scheme to map data to users in a way that is anonymous to database server I am trying to finish a paper on censorship resistant data-sharing systems in semi-centralized ways. I know the below threat model can be mitigated by using decentralized system, but I am looking for a possible theoretic solution for the following, without being able to change the rules.
Consider the following threat model:

A website that allows accounts for journalists to receive leaked documents / data.

Each journalist has an ID on this website (say username, public key, public key fingerprint, whatever will do).

Whistle blowers use those IDs to send leaked data using this website.

The journalists need to be able to log into their accounts on the website and see all the information that was sent to them, like a list of "support tickets" or something like this.

The website should not be able to see that data content in clear text. - this problem is fixable by implementing database encryption with key derived from user password and kept in session, and dumped at the end.

The threat that needs to be fixed: CENSORSHIP OF ACCOUNTS.
The problem with the above system is that journalists accounts are static. They are also public, and known to everyone including the possible censors.
So, a censor with "authority" can easily force the website to "block" account XXX or otherwise make its data unavailable. Regardless the data itself is secure and safe, not read by any party, it can still be made unavailable to the journalist by censoring their accounts.
What I need is a hint in order to implement multiple cryptographic functions in a system that will allow a website to map data to an account anonymously.
Explained in laymen terms (for simplicity):

You go to a website to send some information to user / account: XXX.
Consider the information you send is already encrypted end to end from you to the receiver, so the information itself is not at risk. The only risk is for the information not to reach the receiver.
The website needs to be able to show that data to user / account XXX when they log in and needs to also have a technical impossibility to "freeze" or "censor" the account XXX in order to not receive further information if required by a censor.

I was thinking of zeroproof systems but I have no clear way to implement them. Also, if instead of account names we use whole pubkeys, senders can send encrypted data directly but a censor can force the website to "filter" pubkey X.
So, the base problem remains unsolved.
Even if one would use Time based codes based on OTP that link to certain accounts, a censor could still force the website to identify the journalist account by trying to send some dummy data themselves to that certain account using a time based token.
Ideas? Thanks in advance.

I'm not sure this threat model is realistic, since I would expect an adversary to want to shutdown the entire site, instead of just censoring specific "contributors" :-).
To protect from this (and from the users becoming de-anonymized) one would likely use an anonymity network such as Tor.

The website should not be able to see that data content in clear text. - this problem is fixable by implementing database encryption with key derived from user password and kept in session, and dumped at the end.

The problem with this, is that the data will be unencrypted at the server's location for some time - worse, the server has the key.
Lets assume, that the server is compromised, and malicious:
Then it could easily obtain a copy of every new document, and of old documents by storing the password, when the respective user logs in again.
A solution to this problem would be to have contributors encrypt data using the public key of the recipient.
However, if you use asymmetric cryptography on the client side, someone has to perform the encryption.
You don't want the website to do this for several reasons:

JavaScript (which would likely be required) is a large attack surface - if the server is compromised, and users of the website are required to enable JS, they are exposed to more risk.

If the server is compromised, it could swap the encryption for nothing, without the users noticing.

Therefore, you would likely need an external program, such as gpg or age.
Unfortunately, by now, we have achieved usability levels close to that of encrypted email :-(.

What I need is a hint in order to implement multiple cryptographic functions in a system that will allow a website to map data to an account anonymously.

As I already said, I don't think this is a realistic requirement.
Additionally, I'm not aware of any protocols that solve this problem.
However, ring-signatures could maybe be used to authenticate users. Using ring-signatures, a user could prove that they are part of a larger user-group. Then, the server can't determine which specific user they are, but could allow them to submit documents for upload.
I'm not sure on the specifics, and there are many ways the protocol design of this could go wrong. A first step would be, to determine the exact requirements.


Deterministic symmetric indistinguishable encryption Are there any block-cipher modes (or symmetric encryption schemes in general) that are fully-deterministic, meaning same inputs lead to the same outputs (like for all modes with constant IV) and satisfy any notion of security?

ECB would for example accomplish the first but has no security properties at all) And more specifically: are there any schemes as described above that produce indistinguishable blocks in the presence of an eavesdropper? (This is weaker than CPA security)

I know that there exist papers for the public key setting but I could not find anything for the symmetric setting. Also, I don't need anything like 'searchable encryption', I need specifically the described properties above.

I have done research on this topic but could not find anything useful.

Yes, the most common / secure deterministic encryption is SIV mode, which stands for synthetical IV mode. Here the IV that is used to randomize each message is replaced by an authentication tag (MAC) over the plaintext message. Of course, this means that identical messages will be distinguishable. But if even a single bit of the messages differ then the entire ciphertext will be indistinguishable as the MAC/IV will of course be different.

SIV or GCM-SIV mode are authenticated or AEAD ciphers. So it is also possible to authenticate additional data together with the data to be encrypted. As most authenticated modes they use counter mode (CTR mode) to provide the confidentiality of the message.

As usual, if the plaintext message differs in size then the ciphertext will differ in size as well.

Deterministic, asymmetric encryption exists as well. Here the random value for indeterministic encryption is usually simply replaced by a secure hash over the message.

Closely related are modes of operation such as Bi-IGE (bi-directional infinite garble extension). If any of the bits of the ciphertext is changed then IGE will make sure that all plaintext bits after that will become affected. Bi-IGE will do the same but in both directions - at the cost of using additional operations of the block cipher, of course.


What is the precise NP statement of Zcash? It would be great if you can point out the mathematical formulation or R1CS form of the NP statement of Zcash.

I found your question intriguing enough to take a dive in the source code. Note that I have absolutely no experience with ZCash; I know a few ins and outs of Monero though, and I have done some tinkering with some very simple R1CS systems.

Since the ZCash "Sapling" update, it seems like the knowledge proof protocols are based on the bellman library. Their proofs are conveniently stored in the zcash-proofs directory of the ZCash Rust library. Their individual circuit "gadgets" are in the sapling-crypto/circuit directory, in which you'll find the Spend and Output circuits. These all build upon the other circuits in that directory, among which a SHA256 hash and a blake2s implementation, and ECC cryptography running in a circuit.

All the above should already give you some insight in what happens: the precise NP-statement and the complete R1CS system will be way too long to present in a simple Stack Exchange answer. I think, even presenting all the constraints on a high level would take us to far, but I think that an illustration of a few constraints may give you a lot of insight! For a high-level overview, I think the ZCash blog gives a good starting point. If you want to dive in depth, there's also the protocol specification; especially "4.15: Zk-SNARK statements" will interest you.

From the above blog, these are some high level constraints:

the input values sum to the output values for each shielded transfer.
the sender proves that they have the private spending keys of the input notes, giving them the authority to spend.
The private spending keys of the input notes are cryptographically linked to a signature over the whole transaction, in such a way that the transaction cannot be modified by a party who did not know these private keys.

Let's explore 1, for example.
Each transaction has a sequence of Spend descriptions and a sequence of Output descriptions. The latter is the simplest of both, so let's go with that.

The spec contains four constraints:

Note commitment integrity: the commitment of the note is honestly and correctly generated.
Value commitment integrity: the value commitment of a transaction is the commitment of a value.
Small order check; the point $g_d$ should not be of small order -- implementation detail in the specific curve they use.
Ephemeral public key integrity: the ephemeral public key of the transaction equals $[esk]\times g_d$.

I encourage you to look at the other statements yourself from here; especially the protocol spec is quite detailed in this.


Finding partial pre-image of MD5 hash I have the following requirement for hashing using MD5.

H(A,B,C,X);

Where values A,B & C are given. However X is not given.

I would like to find out what value of X would give a hash beginning with 32 1's bits

meaning H(A,B,C,X) = Begin with 32 '1' bits

I can brute force by testing all kinds of characters of X till i get 32 '1' bits.

however is there a faster way rather than doing this?

Short answer: no you can't, MD5 is not that broken.

Long answer: if you really need to do that, a laptop i5 is able to try 5 millions of MD5 hashes per second; on average you will have to try 2^32 ~ 4300 millions hashes, so that it will be a matter of minutes on any decent remotely-modern CPU.


References about a boolean function involving hamming weight Some weeks ago, I read an article about an interesting boolean function with some applications to cryptography. Then, I forgot about the article and now I cannot find it. Hence here I am asking if someone is familiar with this function and can give me some references. Thank you in advance.
Fix a positive integer $n$. The function boolean function $f$, taking a $n$bits words $\mathbf{x}$ as input and returning a single bit as output is defined by
$$f(\mathbf{x}) = x_{w(\mathbf{x}) \!\!\!\mod\!\! n} ,$$
where $w(\mathbf{x})$ is the Hamming weight of $\mathbf{x}$ (number of bits equal to 1) and $\mathbf{x} = x_0 x_1 \dots x_{n-1}$ (with $x_i \in \{0,1\}$).

It is the hidden weighted bit function. There is more than one paper related to cryptographic applications of this function, but the full definition may be found, for example, in Chapter 3 of this paper:
Cryptographic properties of the hidden weighted bit function


Repeated modular square roots to recover original base I'm given a large prime $p$ and $c \equiv m^e \pmod p$, and $e = 2^{64}$. Typical RSA rules don't apply here, since $\phi(p) = p - 1$ is even, and $e$ is a power of two, so they share a common factor, specifically $\gcd(\phi(p), e) = 2^{30}$. I was thinking of applying repeated modular square-rooting, and since $p \equiv 1 \pmod 8$, I can apply the Tonelli-Shanks algorithm to get two square roots of $c \pmod p$. However, repeating this until I reach $m$ would give me $2^{64}$ possible plaintexts to sift through. I know that the plaintext $m$ is 42 bytes long and I also know the first 6 bytes, and the last byte. How can I eliminate square roots before I go all the way down the "tree"?

How can I eliminate square roots before I go all the way down the "tree"?

The obvious thing to do is eliminate intermediate values that are not quadratic residues.  Here is one way to do it:
Define the set s := [ c ], that is, s initially consists of a single element c.
For i := 0 to 63 do
    Set the set t := [], that is, initialize it to be the empty set
    For each element a \in s
        Use the Toneli-Shanks algorithm to find the square roots b, -b of a$
        Check if b*b = a mod p; this cannot hold if a is not a quadratic residue
        If the check holds, then add b, -b to the set t

    Set s := t

At the end, the set s will consist of all the possible $2^{64}$th roots.
This won't iterate through $2^{64}$ values because the Quadratic Residulosity check will reject about half of the incorrect paths (as half the possible values are not Quadratic Residues)
.  Instead, the sizes of the sets s, t should be reasonable (in my experience based on similar algorithms, possibly hundreds of elements)


Authenticated and encrypted radio communications (Non-Internet or TCP/IP) I'm working on an IoT project that will control lights and eventually other devices (I know there's plenty of projects like this, but that's not the topic here).

Primarily communications will take place over a 900 MHz band radio, probably through an RFM69 type module, or perhaps LoRa. (The radio type shouldn't really matter, just that it will be low bitrate). The MCU will likely be an ESP8266, so only an 80 MHz clock.

Since I care about this being a useful and secure system, I clearly need some security protocol. If it were WiFi and IP based, of course this could be TCP - but that is not as suitable in this case.

I'm looking for something that will provide these features:

Authenticated. Only the owner of the system should be able to control the lights.
Confidential. Someone listening should not be able to deduce usage patterns such as when people turn the lights off when leaving the building.
Replay protected. If someone does observe a control message they must not be able to use that again.

Given the nature of the system, it has these constraints and parameters:

There is one server "hub" with several client "nodes".
Peer-to-peer is not necessary, nodes talk only to the hub.
Connections are unreliable. I plan to use the RadioHead library which does offer "reliable datagrams", but this may not be appropriate for all cases.
The server is configured to "know" the nodes, so can have a pre-shared public key for each.
Each node is configured to "know" the server, so likewise can have a pre-shared public key for the server.
There is no mesh or routing, the nodes can and must always be one hop from the hub.
Packets will never be fragmented. I don't know yet what the size limit will be, but I do not plan to support fragmentation.
Broadcast messages from the hub must be received and decrypted by all nodes as close to the same time as possible (not individually sent).

I've done a fair bit of searching for something that would fit this bill, but so far have come up short. This is what I've considered so far:

PSK Ciphersuites for TLS (RFC 4279): PSK is better than X.509 for small processors, but it still uses RSA, AES and SHA algorithms. I would prefer something that could use something like Ed25519, Speck, Blake from the ArduinoLibs crypto library. Also, it's TLS so each client-server connection has a different key and so a true "broadcast" doesn't work.
Datagram Transport Layer Security (DTLS) (RFC 6347): Haven't read as much into this, but seems to be closer to what I'd need. But, still includes a lot of overhead like re-ordering etc that I won't need, no message can be out of order because there is no routing, only direct radio link.
CurveCP: Seems to be optimised to fit into a small processor, but aims to be like TLS which again includes overhead I don't need for a single hop link.

What else exists for what I'm trying to do? I have some ideas of how I might make my own solution to this, but "roll your own crypto" is always advised against and not something I'd like to take on if I don't have to.

Public-key cryptography has only one advantage in the topology of the question (central server): it allows initial setup across a channel assumed secure from an integrity standpoint only (rather than also confidentiality). But public-key cryptography comes with complexity and performance issues; assuming ability to securely inject a secret key in slave devices, and the slave devices tailored to a single central server, plain old secret-key cryptography seems a good choice.

That would be with a master secret key in the central server, with each slave device assigned an ID and a "diversified" secret key derived from the master secret key and device ID, using some Key Derivation Function (HMAC will do nicely). These long-term keys can then be used to derive session keys, much like long-term public/private key pairs are used to derive session keys. Upon initiating communication with a device giving its ID, the central server can quickly find the slave device's secret key, by applying the KDF.


Prime factorization (102 digits) I have a number that consists of 102 digits and I need to factor it. I ran it in alpertrom.com.ar, but it'll take up to 40 hours if I counted all right. Is there any way to make it by hand (stupid question), I mean to simplify computation for the program? Or maybe anyone can factor it out. The professor is probably just testing our processor's computability.
Here's the number: 166045890368446099470756111654736772731460671003059151938763854196360081247044441029824134260263654537

Your 102-digit nuber is two digits more than the first RSA challenge RSA-100 that has 330-bit.
This can be easily achieved with existing libraries like;

CADO-NFS ; http://cado-nfs.gforge.inria.fr/

NFS factoring: http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html

Factoring as a service https://seclab.upenn.edu/projects/faas/

The Factoring as a Service project is designed to allow anyone to factor 512-bit integers in as little as four hours using the Amazon EC2 platform for less than $100, with minimal setup.

The experiment
Factor of a 99 digit number
$n =$ 112887987371630998240814603336195913423482111436696007401429072377238341647882152698281999652360869.

I have tried with Pollard's $p$ -1 algorithm, still running for one and a half-day and did not produce a result, yet. This is what expected due to the B bound must be around $2^{55}$ with success probability $\dfrac{1}{27}$. I've stopped the experiment after the CADO-NFS succeeds. This is self-implemented Pollard's $p$ -1, one can find an optimized in GMP-ECM

Tried the CADO-NFS. The stable version may not be easily compiled for new machines, so prefer the active one from the GitLab.
After ~6 hours with 4 cores, CADO-NFS produced the result. This was an RSA CTF/Challange and I don't want to spoil the fun; here the hash commitments with SHA-512, it is executed with OpenSSL;
echo -n "prime x" | openssl sha512

27c64b5b944146aa1e40b35bd09307d04afa8d5fa2a93df9c5e13dc19ab032980ad6d564ab23bfe9484f64c4c43a993c09360f62f6d70a5759dfeabf59f18386

faebc6b3645d45f76c1944c6bd0c51f4e0d276ca750b6b5bc82c162e1e9364e01aab42a85245658d0053af526ba718ec006774b7084235d166e93015fac7733d

Experiments on RSA challenges with 6 cores using CADO-NFS

RSA Challange
Bit size
Time in minutes

RSA-100
330
270

RSA-110
364
280

RSA-120
397
1049

RSA-129
426
3279

RSA-140
430
Not tested

The core count is very important to reduce the time as 512-bit can be broken as 4 hours in the EC2 platform.

Details of the experiment

CPU : Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz

RAM : 32GB - doesn't require much ram, at least during polynomial selection and Sieveing.

Dedicated cores : 4

Test machine Ubuntu 20.04.1 LTS

CUDA - NO

gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)

cmake version 3.16.3

external libraries: Nothing out of Ubuntu's canonicals

CODA-NFS version : GitLab develepment version cloned at 23-01-2021

The bit sizes;

$n$ has 326 bits
$p$ has 165 bits
$q$ has 162 bits

The cado-nfs-2.3.0 did not compile and giving errors about HWLOC-  HWLOC_TOPOLOGY_FLAG_IO_DEVICES. Asked a friend to test the compile and it worked for them. It was an older Linux version. So I decided to use the GitLab version.

Note: this question did not factor the OPs original number.

Historical note: RSA-100 challenge has 330 bits and broken by Lenstra in 1991.


Counting points on elliptic curve over binary field How to count number of rational points on elliptic curve over binary field?

Counting number of points on elliptic curve over $\mathbb F_2$ is very easy.For extension of fields we can use of this theorem:

Theorem : Let $E$ be an elliptic curve defined over $F_q$, and let $\#E(F_q ) = q +1−t$.
Then $\#E(F_{q^n} ) = q^n + 1 − V_n$ for all $n ≥ 2$, where $\{V_n\}$ is the sequence defined
recursively by $V_0 = 2, V_1 = t$, and $V_n = V_1V_{n−1}−qV_{n−2}$ for $n ≥ 2$.


Looking for a specific cryptosystem (encryption two times with two different keys and then decryption with another different key ) I am looking for a specific cryptosystem with the following properties:

Suppose a User (Say $User_1$) encrypts a message $M$ with the key $K_1$ (the resulted ciphertext is $C_1$). Another user, say $User_2$, encrypts the ciphertext $C_1$ with another key $K_2$ (the resulted ciphertext is $C_2$).
Now, a third user (e.g., $User_3$) should be able to decrypt $C_2$ with the key $K_3$ to achieve the message $M$.

$C_1 = E_{K_1}(M)$

$C_2 = E_{K_2}(C_1)$

$M = D_{K_3}(C_2)$

Note: The keys may be related to each other, but they should be three different keys.

The standard answer to this is the Pollig-Hellman cipher.

Here's how it works; you have a large public prime $p$, and each key $k$ is a value relatively prime to $p-1$.  Then, we have:

$$E_k(M) = M^k \bmod p$$

$$D_k(M) = M^{k^{-1} \bmod p-1} \bmod p$$

What this means is that we have:

$$E_{k_2}(E_{k_1}(M)) = E_{k_1 \cdot k_2 \bmod p-1}(M)$$

So, what you would do is have your TTP generate the three keys $k_1, k_2, k_3$ with $k_3 = k_1 \cdot k_2 \pmod {p-1}$, and you have the relation you're looking for.


How to convert from small field to large field If I have number $2$, which is additively shared into $3+4 \bmod 5$.
Now I need to change the filed to a large one, like $500$.
How to convert the shares, so that I can have a new number or shares $a+b \bmod 500 = 3+4 \bmod 5$.

I think that what the OP is thinking about is a $(2,2)$ additive secret-sharing scheme in which a secret $S$ is split into two shares $X\neq 0$ and $S-X\neq S$. Here, $X$ is an arbitrarily chosen nonzero integer. Neither share holder can determine the value of $S$, but when both shares are submitted to the trusted reconstructor, the reconstructor can recover $S$ as the sum of the two shares.  In the OP's scheme, $S=2$ is split into shares $3$ and $4$ where right-handed folks can assume that $X=3, S-X=4$ while left-handed folks can assume that $X=4, S-X=3$ and all of these elements are assumed to be elements of $\mathbb F_5$. Thus, the secret $S = (X) + (S-X)$ (which has value $7$ in ordinary integer arithmetic) is also  an element of $\mathbb F_5$ and works out to be the correct value $2 \in \mathbb F_5$.
The OP then wonders

Assuming that the secret $S$ continues to have value $2$, what should the share values $a$ and $b$ be so that $a+b = 2\bmod 500$?

Note that we do not necessarily have to have a field of order $500$ (as the OP mistakenly assumes exists) for this simple additive secret-sharing scheme; the additive group $\mathbb Z_{500}$ will work just fine. So, the answer to the OP's query is that the share values can be any two integers whose sum is $2$ modulo $500$. For example, the shares could be $(a,b) = (3,499)$ or $(a,b) = (498,4)$ if we choose to keep one of the two share values the "same" as before; with quotation marks around same to remind folks that $3,4,498, 499$ are elements of  $\mathbb Z_{500}$, not $\mathbb F_5$. It is, of course, an added bonus that $a+b\mod 500 = a+b \mod 5$. But other choices would work equally well; $(a,b) = (251,251)$ will stop juvenile bragging rights arguments among share holders ("neh, neh, ni, neh, neh, my share is bigger than yours!").


How do you get the original salt after it's been hashed to the user's password in the database? I'm researching how to do salt and hashing.  I'll be using SHA256.  Here is what I found:

  To Store a Password

  Generate a long random salt using a CSPRNG.
  Prepend the salt to the password and hash it with a standard password hashing function like Argon2, bcrypt, scrypt, or PBKDF2.
  Save both the salt and the hash in the user's database record.

  To Validate a Password

  Retrieve the user's salt and hash from the database.
  Prepend the salt to the given password and hash it using the same hash
  function.
  Compare the hash of the given password with the hash from the database. If they match, the password is correct. Otherwise, the password is incorrect.

My question is: How do you get the original salt after it's been hashed to the user's password in the database?  You can't "unhash" the salt and add that to the password they've entered and then hash.  Wouldn't you get a different result?

Did you read what you found? Quote: Save both the salt and the hash in the user's database record. and Retrieve the user's salt and hash from the database.

So, you simply store the original salt you used to the database, from where you can later read it. There is no need to "unhash" anything as you have the original salt available at all times… stored next to the salted hash in your database.

More practical:

Let's say for some user you use salt 123 and hash the user password with that salt. You then store both 123 and the hash result to your database:

ID   | salt | hashResult
-----+------+-------------
1    | 123  | F7A4…

When you later want to compare some password, you read the stored salt 123 and hash the password you want to compare using that salt you have previously stored in your database.

In simpler words, this roughly boils down to:

Does "User input hashed with stored salt 123" produce the same result as "the stored hash value"? If the answer is "yes" because the resulting hash matches the hash value you previously stored, the passwords match… if the answer is "no" because both hash results are different, the passwords don't match.

I guess what you've missed is that you always have the salt available — stored next to the related password hash. If you wouldn't do that, you would indeed not be able to recover the salt later on.

Also note that storing the salt in your database next to the hash result isn't a problem because a salt is not a "secret", while the password is a "secret".

For more information on what a salt is and what it does, check "Can you help me understand what a cryptographic “salt” is?"


Proof of possession. x25519 + ed25519 There are Client and Server.

Client have previously send public keys for x25519 and ed25519 to the server. And now need to prove that it has private keys for them.

I have found similar solutions in description of ssh protocol by Digital Ocean: https://www.digitalocean.com/community/tutorials/understanding-the-ssh-encryption-and-connection-process#authenticating-the-user's-access-to-the-server

And in SSH Authentication Protocol RFC: https://tools.ietf.org/html/rfc4252#section-7

General scheme:

Server generates some 'nonce'. Encrypts it with x25519 public key of the client and sends to the client.
Client decrypts the 'nonce' with corresponding x25519 private key. Signs it with ed25519 private key and sends original data with the signature attached.
Server checks that the data equals to the one was send in (1). And checks signature. Proof-of-Possession is done.

I have two questions:

Is this scheme correct ? What should I review/read to make it correct ?
In the article from Digital Ocean you can find that client doesn't send raw data back to server but gets md5 of it and sends only md5. Why so ? What's the point of that operation ? Should I do the same ?

Is this scheme correct ? What should I review/read to make it correct ?

One obvious issue is that the client is willing to decrypt arbitrary ciphertexts with its private key.  Hence, if it uses the private key for any other purpose, well, it's insecure.

  In the article from Digital Ocean you can find that client doesn't send raw data back to server but gets md5 of it and sends only md5. Why so ?

Well, that's to prevent someone from using the client as a decryption Oracle; they still could use it as a "decrypt-and-MD5" Oracle, but that's not nearly as bad.

Personally, I would make three changes:

Replace MD5 with a modern hash (for example, SHA-256) - while MD5 is probably perfectly safe in this use, it has shown enough weaknesses that steering clear is probably the wiser option.
I'd replace the deterministic hash with a randomized one.  That is, I'd have the client pick a random string "r", and return the pair $r, SHA256( r || decryption )$.  That way, the client can't be used as a "decrypt-and-SHA256" oracle either.
On decryption failure, I'd make sure I'd pick a random decryption, and return the pair $r, SHA256( r || random )$ - there's no reason to give people a "is this a valid ciphertext" Oracle.

Actually, personally I'd probably replace this entire thing with a Schnorr proof of knowledge, but I rather assumed you didn't want to wholesale replace everything...


Discrete logarithm hash function Exercises I have a problem with this exercise:

Let $G$ be a group of order a prime $q$ and let $g, h$, be two randomly selected elements of $G$, with $g,h\ne 1$. Consider the following hash function on integers $x_1$ and $x_2$:
$H(x_1,x_2)=g^{x_1}h^{x_2} $
Show that the problem of finding a collision pair $(x_1',x_2')$ such that $H(x_1, x_2) =H(x_1',x_2')$ is equivalent to finding the discrete logarithm of $h$ with respect to the base $g$ (or viceversa, of $g$ w.r.t. the base $h$).

I thought I could do this to solve the problem:
$log_g(h)=x$ then $h=g^x$
If $H(x_1,x_2)=g^{x_1}h^{x_2} $ then I can write:
$H(x_1,x_2)=g^{x_1}{(g^{x})}^{x_2}=g^{x_1}g^{xx_2}=g^{x_1+xx_2}$
With $x$ fixed, it is simple to find a pair of $(x_1',x'_2)$ such that $x_1'+xx_2'=x_1+xx_2$ and then a collision.
Can you tell me whether this logic works? Do you know if there are easier ways to solve it?

Yes, this logic works. You have shown that given the discrete log $x$ lets you easily find collisions. Now you need to show that any collision lets you extract the discrete log $x$ and then you are done (then you have shown the equivalence).


RSA digital signature vs authenticated cipher I want to provide both confidentiality and integrity for data at rest (many large files stored on disk).

I plan to encrypt the data using AES, which will cover the confidentiality requirement.

So the issue is how to provide integrity:

Instead of AES, use AES-GCM-SHA256 (authenticated cipher). My understanding is that this produces an HMAC (keyed hash) of the encrypted data (and IV), and appends it to the end of the file
After encrypting each file, produce an RSA digital signature and either save it as a seperate file or append it to the encrypted file

What are the merits and disadvantages of each option?

You got some notation wrong. There is no algorithm like "AES-GCM-SHA-256".

AES is a block cipher, i.e. a pseudorandom permutation of 128-bit blocks. It itself only allows encryption for messages of size 128 bits (= 16 bytes), with a limited security guarantee.

When you mean "encrypt the data using AES", you actually mean "use AES with some mode of operation to encrypt the data".

Galois/Counter Mode is one such mode of operation, which combines counter mode for privacy and a block-cipher based MAC (GMAC) using some finite field operations and some block cipher calls for authentication.

SHA-256 is a hash function, but neither it nor its associated HMAC function HMAC-SHA-246 are used here in any way.

When using GCM (or almost any mode) for disk encryption with changing files, you should pay attention: You shall not use the same key and initialization vector (= initial counter) twice for different data. This also means, don't simply change some parts of the file an then encrypt again only the changed parts with same initialization vector, as you are then using the same IV twice (over time).

Instead, either generate a new random IV and encrypt the whole file with it, or split the file in blocks (of a comfortable size, e.g. 4 KB or such), each of which is then encrypted using GCM mode with a separate, independent random IV.
(This works better if you are encrypting your whole disk – then you would use the disk sector as your encryption unit.)

There is no point of using a signature – that only makes sense if you want to allow someone else to prove that you did produce (or at least sign) the data, without this one being able to produce it himself.


Difference between a circuit and a normal function I've seen the word circuit used in many crypto contexts (for example, regarding FHE in this pdf). I've always thought of a circuit as another word for a program or function. But is there a difference - i.e., is there something that a standard function can do that a circuit can't?

A circuit is a representation of a (computable) function. There are many other ways to represent a function (mathematical notation, Turing machines, pseudo-code, etc.), but for some purposes it happens that circuits are the most convenient one.


Does the exact distribution of padding bytes in PKCSv1.5 type 1 matter? [Disclaimer: I am fully aware PKCSv1.5 is horrible and should die (though tell that to the TLS v1.2 specification). I am asking this question for my own edification.]

PKCSv1.5 encryption padding (as seen for instance in RFC 3447) formats the RSA message representative as

EM = 0x00 || 0x02 || PS || 0x00 || M

Where PS is at least 11 bytes taken from $[1...255]$ (i.e., no zero bytes are allowed). In most implementations I have seen, this is done by rejection sampling, i.e. the RNG is sampled repeatedly and bytes consisting of $\texttt{0x00}$ are skipped.

My question is the following: if PS is generated from a non-uniform distribution, are there any security issues that arise? As a concrete example, take PS to be the output of a CSPRNG but whenever the RNG outputs a $\texttt{0x00}$, instead of resampling the RNG just take $\texttt{0x01}$ as the output instead. So $\texttt{0x01}$ bytes will appear twice as often as normal. Yet this statistical abnormality in the padding does not seem to lead to any practical attack I am aware of.

References to any attacks in this line are welcome. For example if the padding bytes are derived using a LCRNG, does that cause any problem? (It certainly seems like a horrible idea, but again I'm not aware of any specific attack.)

In practice this should be okay. The reason the padding needs to be random is that if the padding can be guessed then the attacker can start encrypting candidate plaintexts (correctly formatted with the padding) under the public key and observe if the output matches the target ciphertext. Of course if the attacker finds a match then they have recovered the plaintext.

If the padding is 11 bytes of purely random padding that can take any value in $[1, 255]$ this means the attacker will have to do $255^{11} \approx 2^{88}$ encryptions for every candidate plaintext they want to check, which is clearly computationally intractable.

By sampling in the range $[0, 255]$ and replacing $\tt{0x00}$ with $\tt{0x01}$ you still have $255^{11}$ possible paddings but there are now some bytes that are more likely to occur than others (e.g. the first byte is more likely to be $\tt{0x01}$ than $\tt{0x02}$) so the attacker could optimize the order in which they check encryptions of padding / plaintext combinations.

If you are deriving padding bytes via a LCRNG this can lead to much worse results since there are ways to predict the output of a LCRNG. This in turn would reveal the padding to the attacker and instead of $255^{11}$ guesses per candidate plaintext they would only need $1$. In a sense when the padding is known the scheme degenerates to textbook RSA, and as such carries with it the same issues.


K out of N encryption A friend just showed me how to combine padlocks to achieve a lock that opens when k out of n people turn their keys.

I was wondering if there was something similar for encryption; using n or fewer public keys encrypt a piece of data so it can only be unlocked if at least k out of n specific private keys are applied.

I've tried ideas of stacking normal public key encryption, but without luck. I'm sure somebody must have done research on the topic, but I have no idea what such a thing is called. Maybe it's even widely accessible through standard encryption libraries?


one-time pad key related attack In one-time pads we always say do not use same key twice to encrypt ASCII messages, but if we use a random key to XOR a random binary message and then reusing the same key for XORing new random messages will compromise our key ? Or is attacking reused keys for random messages infeasible?

Once you've XORed two messages with the same secret value, the net result is the same as if you had XORed them with each other without using the secret at all.

Given $plaintext_1$ ⊕ $key$ = $cyphertext_1$ and $plaintext_2$ ⊕ $key$ =  $cyphertext_2$, then $cyphertext_1$ ⊕ $cyphertext_2$ == $plaintext_1$ ⊕ $plaintext_2$.  Because it's XORed twice with the same key, the double XOR becomes the identity function and the key is simply factored out.

If the attacker learns any bits of the plaintext of either message, they can recover those corresponding bits of plaintext from the other cyphertext message, plus they can recover those bits of the key as well.

So it falls to you to determine if $cyphertext_1$ or $cyphertext_2$ have any knowable information in them.  It's completely irrelevant if the plaintext data is ASCII, binary, or EBCDIC.  If an attacker can discover or guess what any piece of the data is, it's vulnerable.

This is the classic weakness with the Vernam cypher, and is what enabled the Venona decryption of Soviet secrets.  And it's why it's no longer a one-time pad cypher if you use either the plaintext or the key more than one time.


What is safer: ZipCrypto or AES-256? Like in title: which one of these encryption methods (ZipCrypto, AES-256) is more secure and why? I am asking about it because I'd like to know which should be preferred when compressing files with Zip.

According to 7-Zip,

  Use ZipCrypto, if you want to get archive compatible with most of the ZIP archivers. AES-256 provides stronger encryption, but now AES-256 is supported only by 7-Zip, WinZip and some other ZIP archivers.

So really there is some balance to be played with. Do you require better security at the sacrifice of compatibility or more compatibility at the sacrifice of security?

According to the Info-Zip FAQ, it sounds like ZipCrypto is pretty weak. Keep that in mind when making your decision.

Note: The link on Info-Zip FAQ to the publication is broken, you can find the file on A Known-Plaintext Attack on the PKZIP Stream Cipher


Is there an encryption method where the order of decryption is irrelevant to the order of encryption? With most encryption methods, if a message is encrypted first using key $k_1$ and then using $k_2$, to decrypt it you have to use first $k_2$ and then $k_1$.

I was wondering if there are any encryption methods that can be decrypted using the keys in any order. For example, if a message is encrypted using the keys $k_1$, $k_2$ and $k_3$, in this order, then it could be decrypted in the order of $k_2$, $k_3$, $k_1$ or in any other order, as long as all 3 keys are used.

Simple XORing the keys and the message is possible (where the key space is the same as the message space) but if multiple messages are encrypted, it is not secure.

So my question is: Is there an encryption method where the order of decryption is irrelevant to encryption, but which is also secure with multiple messages? The size of the keys doesn't matter.

Any synchronous stream cipher, or block cipher in a stream-like mode of operation (such as counter-based modes), will have this property. That's because they are, in essence, stretching a user-supplied key to an arbitrary length, and then using it as an XOR mask to encrypt (or decrypt) the message. Since the message content isn't relevant to cipher stream, and the actual encrypt/decrypt operation is just XOR, the order is unimportant.

Note that ciphers like this are extremely vulnerable to some classes of attacks, such as a bit-flipping attack. It is therefore crucial that you include an integrity check, such as an HMAC, with your ciphertext.

In order to make this secure with multiple messages, you have to do the same thing you do with most ciphers when reusing a key: you need a new nonce or initialization vector (IV). This value is randomly generated for each message, and sent along with the ciphertext in the clear. It is useless for the attacker unless the attacker also has the key, but it allows the same shared key to produce different ciphertexts even when encrypting the same plaintext message. This means an attacker can't determine anything about the plaintext (other than its length, which can be mitigated via padding and so on) by comparing ciphertext messages, even if the attacker knows they were encrypted with the same key.

You do need to be absolutely sure to never re-use the IV, though. IV re-use makes it quite easy to break many crypto schemes. For example, the old Wired Equivalent Privacy (WEP) encryption used for early WiFi had short IV (only 24 bits) and this was weak enough that often possible to break the encryption with only a few minutes of analysis if the network was busy (and therefore had to generate a large number of IVs to encrypt all the packets it was sending).

With all that said... schemes like you describe aren't as secure as you might expect them to be. While they should remain at least as secure as only doing a single round of encryption, they might not be any better than that. Due to attacks such as meet-in-the-middle, using the same cipher for multiple operations (even with different keys) is less secure than you'd expect. Mixing encrypt and decrypt operations is more secure for ciphers where encrypt and decrypt are different operations (which is not the case for cipher classes mentioned above) but even then, it's less secure than you might expect. A real-world example of this is the Triple-DES cipher, which attempts to fix the weakness of the DES cipher's 56-bit key by using three keys, and doing encrypt-decrypt-encrypt (or the reverse, for the decrypt operation). You might think that would produce 168 bits of effective security, but due to meet-in-the-middle, it's actually only 112 bits effective (although you do still need all three keys to be distinct, which is 168 bits of key material).

Still, if you want to generate a bunch of independent keys, encrypt a message with all of them, and then require them all to be re-entered before the message is decrypted without caring about the order of re-entry... this scheme should work. Just don't expect it to be more resistant to cryptanalysis than just encrypting the message once.


DES- If LSB is removed, are the key B and C the same? I believe that in DES every 8th bit is ignored of the key. That means B and C are same if the LSB is ignored. So, shouldn't encrypting a message by the key all Bs be able to be decrypted by key with all Cs? I tried doing it but did not work. I used this tool to check : http://extranet.cryptomathic.com/descalc/index

The ASCII letters B and C are represented by the bytes 0x42 and 0x43, which indeed are equivalent in a DES key since they differ by the low-order bit only. However the tool used accepts keys in hexadecimal, and the byte 0xBB and 0xCC are not equivalent key bytes for DES.


Interleaving bytes to make an effectively larger block size Will applying a 16 byte bit block cipher such as AES over a 256 byte block to in the following way result in a much stronger cipher:-

Apply block cipher with first key digest to each 16 byte group.
Then interleave the bytes.  I.E. Place the bytes horizontally into a 2D (16 times 16) byte array and then remove the bytes vertically so that each new 16 byte group now has one byte of each of the old 16 byte groups.
Then apply block cipher with second key digest.
Then interleave.
Then apply block cipher with third key digest.

Alternative 1, Interleave = ShiftRows

Use a KDF for extending and splitting the input key into three keys $K_1, K_2, K_3$.
Split the input into $A_0 = a_0..a_{15}, A_1 = a_{16}..a_{31},...,A_{16} = a_{240}..a_{255}$
AES-ECB encrypt using key $K_0$ so that $E_{K_0}(A_i) = B_i = b_{16i+0}..b_{16i+15}$
Interleave so that $c_{16i+j} = b_{16(i+j)+j \bmod 256}$

The problem here is that if $A_i = A_j$ for all $0 \le i, j \lt 16$, then $C_i = C_j$ for all $0 \le i, j \lt 16$. This equality will propagate through all three rounds, making it easy to distinguish your 2048-bit composite function from a random 2048-bit permutation with only a single query.

Clearly, if $A_i = A_j$, then $E_{K_0}(A_i) = E_{K_0}(A_j) = B_i = B_j$. This means that $b_{16i+k} = b_{16j+k}$ for all $0 \le k \lt 16$. If this relation holds for all $0 \le i, j \lt 16$ then, for each $0 \le k \lt 16$, $b_{16i + k} = b_{16j + k}$ for all $0 \le i,j \lt 16$.

In particular, $b_{16i+j} = b_{16(i+j)+j \bmod 256}$.

In other words, if $A_i = A_j$ for all $0 \le i, j \lt 16$, then the interleave step will be the identity function. The composite function will for such inputs only consist of three consecutive AES-ECB operations.

Alternative 2, Interleave = Transpose

Use a KDF for extending and splitting the input key into three keys $K_1, K_2, K_3$.
Split the input into $A_0 = a_0..a_{15}, A_1 = a_{16}..a_{31},...,A_{16} = a_{240}..a_{255}$
Round = 0
AES-ECB encrypt using key $K_0$ so that $E_{K_0}(A_i) = B_i = b_{16i+0}..b_{16i+15}$
If round = 2, exit
Interleave so that $c_{16i+j} = b_{16j+i}$
round = round + 1, $A = C$ jump to step 4.

In this case, if $A_i = A_j$ for all $0 \le i,j \lt 16$, then, in the first round = 0, $c_{16i+j} = c_{16i + k}$ for all $0 \le i,j,k \lt 16$. This means that after the second round = 1, there are only $2^8$ different values for the $B_i$ blocks.

Hence, find two 128 bit values $A$ and $A'$ such that $E_{K_0}(A) = b_0..b_{15}$ and $E_{K_0}(A') = b'_0..b'_{15}$ differ only in a single byte $b_i \neq b'_i$, and such that $E_{K_1}(b_i..b_i) = c_0..c_{15}$ and $E_{K_1}(b'_i..b'_i) = c'_0..c'_{15}$ are equal in two different byte positions $c_j = c'_j$ and $c_k = c'_k$. If this happens, the two inputs to the composite function that consist in sequences of $A$ and $A'$ respectively, will result in two output, such that both the $j$th blocks and the $k$th blocks are identical. The probability two random 128 bit blocks will have this relation is $\frac{16}{2^{8\times15}}\times\frac{16\times15}{2^{8\times2}}$, which is significantly greater than the probability that you would get the same relation between the corresponding outputs of a 2048 bit pseudo random permutation, and great enough to expect to get such a relation after only $2^{64}$ attempts.


Where is the S-Box generated in Rijandel/AES? It's rather kind of lame questions, and I can't find good and clear explanation:

In which step of Rijandel is S-box generated?
Is the S-box reused in every round of cipher or is generated in every iteration?
In a course-ware movie where they explained AES (class.coursera.org/crypto-preview/lecture/16) the speaker says that the S-box could be precomputed. Does that mean that the S-box could be constant?

The S-Box was generated when Rijndael was designed, not in any step.
It's used in every round in the SubBytes step.
The S-box is constant. You could see it as a function taking a byte and returning a byte. It is used to reduce algebraic properties of Rijndael.

In fact, this is it:

   | 0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|
00 |63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
10 |ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
20 |b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
30 |04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
40 |09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
50 |53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
60 |d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
70 |51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
80 |cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
90 |60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
a0 |e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
b0 |e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
c0 |ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
d0 |70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e0 |e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
f0 |8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16

You can read it by choosing your column by the low nibble of a byte, and the row by the high nibble of a byte.


Are Merkle Dags really Dags in most cases? Let $H$ a cryptographic hash function of image length $n+1$ and $s_0$, $s_1$, ... , $s_k$ a finite sequence of bitstrings (length $>n+1$), such that $s_j$ contains a hash of $s_{j-1}$ for all $1\leq j \leq k$, that is $\langle s_j(0),...,s_j(n)\rangle = H(s_{j-1})$ (The first $n+1$ bit of each $s_j$ are the hash of $s_{j-1}$).

Is it possible and if yes how likely, that the sequence $s_0$, $s_1$, ... , $s_k$ is a loop? I.e. that $s_0=s_k$?

Edit: If important for the answer, $s_j$ must not necessarily begin with the hash of $s_{j-1}$ but contain it at least at a fixed position in the bitstring. The soley point of the question is to find Merkle DAGs/Trees which are not well defined due to the existence of those cycles.

If its infeasible, I would like to see a deduction from the axioms of a cryptographically secure hash function.

Edit: Relating the question to the title: If such a loop can be found as a path in a Merkle Dag (or in the extrem case a Merkle tree), then the resulting data structure is neither a tree nor a dag anymore.

Edit-2: From Fixed point of the SHA-256 compression function we know that fix points of cryptographic hash function can be found, so it might also be possible to come up with bitstrings $s_0$ of length $>n+1$ that contain their own hash in the first $n+1$ bits. So it is indeed possible to find those loops with $(s_0,s_0, \ldots, s_0)$ for arbitrary $k$'s. In fact the answer from Is there a string that's hash is equal to itself? estimates that this happens frequently (The answer assumes strings of length $n$, but can be extended to our case)

So it boils down to the question of the possibility to find strings strictly larger then their hash, that nevertheless contain their hash as a substring.

It is certainly possible for a string to contain its own hash value, so it's even possible that $s_0 = s_1$.

And it's even possible to artificially construct functions that satisfy all the standard properties required of a cryptographic hash function (i.e. collision and first and second preimage resistance), but which hash an arbitrarily chosen string to a prefix of itself.  All you need to do take any standard secure cryptographic hash function and redefine its output for that single arbitrarily chosen input, as in fgrieu's answer to this related question.

However, no examples of such strings are known for any cryptographic hash function that is widely used and currently believed to be secure, such as SHA-2 or SHA-3.  Indeed, arguably, the ability to exhibit such a string would strongly suggest some kind of a weakness in the hash function, since finding such a string purely by brute force would be completely infeasible for any hash function with a reasonable output length (say, 256 bits or more).

Indeed, the same holds for longer cycles as well: as far as I know, for a random hash function $H$ with $n$-bit output, there's no way to find such cycles more efficiently than by using a generic cycle finding algorithm, all of which require at least $2^{n/2}$ evaluations of the hash function on average.

Finally, I should note that none of this necessarily has any relevance to whether or not Merkle DAGs or trees are well defined, as it's perfectly possible to define those structures in a way that allows two distinct nodes to have the same hash and/or the same children and/or content.  For example, the definition of a Merkle tree currently given on Wikipedia reads:

  [A] Merkle tree is a tree in which every leaf node is labelled with the hash of a data block, and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes.

While this definition is rather terse, and glosses over some important details (some of which are addressed later on the page), the key point is that under this definition a Merkle tree would remain a tree even if all the nodes happened to have the same label, since the labels have no effect on the graph structure of the tree!

Of course, a secure implementation of a Merkle tree should not allow an attacker to feasibly construct two nodes with different children and/or contents but the same label, at least not on the same level of the tree, since swapping one such node for the other would then allow a forgery.  But even an insecure implementation that did allow that would still be well defined.

Conversely, even if you defined a Merkle tree (or DAG) in such a way that the connectivity of the tree was determined by the labels (i.e. such that a node $A$ was defined to be a child of node $B$ if and only if $B$'s label contained the hash of $A$'s label) then, as noted above, as long as you used a secure hash function with no known ways to find cycles faster than by brute force, you could still be practically certain that the resulting structure would indeed be acyclic.

A more serious conceptual issue with such a definition, of course, is that most non-leaf nodes of such trees would have an infinite — or at least a very, very large — number of possible children, simply because hash functions are non-injective and most hash values have infinitely many possible preimages, or nearly so.  Of course, for a secure hash function, finding most of those preimages should be computationally infeasible, but theoretically they still exist.

In practice, to put such a definition on a solid conceptual footing, you'd probably have to restrict the valid node labels to only those appearing in some kind of a global database of known strings indexed by their hash, and then explicitly require that it be infeasible for an attacker to find a string outside the database that shares a hash value with any string in the database.  Fortunately, this is a direct corollary of collision resistance (even assuming that the attacker can add strings to the database; otherwise second preimage resistance would be sufficient), and thus already (presumably) satisfied by any (presumably) secure cryptographic hash function.


Why is Boneh-Franklin IBE scheme secure? What should an adversary do to break it? Even after reading their paper I am still not able to understand why the scheme is secure and what an adversary should do to break it. This question might look stupid to most of you but I don't have mathematics background to delve this deep into cryptography.

The proposed scheme is IND-ID-CPA secure and is semantically secure in a random-oracle model.
From the paper:

The proof of security for our IBE system makes
use of a weaker notion of security known as semantic security (also known as semantic security against
a chosen plaintext attack). Semantic security is similar to chosen ciphertext security (IND-IDCCA) except that the adversary is more limited;

And detailing IND-ID-CPA:

We say that an identity-based encryption scheme $E$ is semantically
secure (IND-ID-CPA) if no polynomially bounded adversary $A$ has a non-negligible advantage against
the Challenger in the following IND-ID-CPA game:

The paper then goes into detail (which I suppose you've read).  But basically the game involves the adversary not being able to better than guess the value of an encrypted bit for a chosen public key.  The adversary has access as to as many other public/private keys as it wants.
The scheme is not IND-CCA secure.  As per this answer here one way to attack the scheme would be to gain access to a "decryption oracle".


Leading 00 in RSA public/private key file I found these following values ALWAYS have the leading 00 in public/private key,

  public key: modulus

  private key: modulus, p,q, d mod (p-1), d mod (q-1), coefficient

e.g., modulus

0007:    02 81 81                               ; INTEGER (81 Bytes)
000a:    |  00   <= the leading 00
000b:    |  da ff 24 57 07 8a 4c b8  63 79 79 ff 55 27 10 15
001b:    |  0f 6c ab 0e 17 dc 05 1a  d3 4f 85 77 6c a6 89 37
002b:    |  8c 83 11 3d 5e 11 15 4b  34 5e 5c dd fd 3f a6 dc
003b:    |  6e 3e ff 97 be 5b 49 2a  78 10 f1 bf 80 d6 09 36
004b:    |  34 bd 99 5f 40 d6 1c 41  8d 3a d8 75 b9 53 b2 40
005b:    |  fb e6 97 72 31 f7 bf 81  5e 75 04 e7 35 0d 98 3b
006b:    |  54 83 3f 9d e8 66 3b e6  2f c9 63 98 63 9f d7 88
007b:    |  99 85 75 d1 21 24 e9 1a  9e 3c da 41 7e 92 5f f1

Could someone tell me why RSA public/private key need the leading 00 ?

You are looking at the ASN.1 encoding of private (and public) keys; the 00 values you see are an artifact of how ASN.1 encodes integers.

ASN.1 is a method for describing data structures, and has ways to represents all sorts of data types.  It wasn't designed with public keys (or cryptography) in mind; it was intended for more general use, initially telecommunications. When it encodes an integer, it has the ability to represent a negative integer.

When we use the BER encoding rules for ASN.1 (which is how ASN.1 are usually encoded in practice), here is how it may represent an integer:

<Tag> <Length> <Value of the integer>

where:

<Tag>: 02 is the magic value for "this is an integer"
<Length>: 81 81 is a variable sized length field that says how many bytes are in the binary value
<Value of the integer>: 00 da ff ... 5f f1 is the binary encoded integer value, in signed big endian form

This is called a Tag-Length-Value encoding or TLV in short.

Now, the rules say that if the most significant bit of the <Value of the integer> field is a 1, the encoded integer is negative (using two's-complement encoding); if it is 0 then the integer is positive (or zero).

Here are the implications of that; if we were to encode the modulus you state as a 256 byte binary value, we would have the binary value as da ff 24 ... 5f f1.  However, if we were to use that as the representation, the decoder would look at the most significant bit of the first byte (da), see that the most significant bit is 1, and interpret that as a negative integer.

In this case, it is required to encode this as a 257 byte binary value, and have the binary value include a leading 0, that is, as 00 da ff 24 ... 5f f1.  In this case, the decoder would look at the most significant bit of the first byte (00 in this case), see that the most significant bit is 0, and interpret that as a positive integer.  And, since adding a leading zero doesn't change the represented value, the decoded integer would be the one we want.

This happens whenever the encoded integer is a multiple of 8 bits in length.

We typically select RSA modulus sizes which are powers of two or small multiples thereof (1024, 1536, 2048, 3072, etc), and so this typically happens there.

And, when we select the primes, we typically split the primes evenly.  For example, when we generate a 2048-bit RSA key, we would typically select two 1024 bit primes; these primes are hence typically multiples of 8 bits in length. And at least one, usually both, must be towards the higher end of the noninclusive range $(2^{1023}, 2^{1024})$ to ensure $n$ is over $2^{2047}$.

The other CRT parameters ($d \bmod p-1$, $d \bmod q-1$, $q^{-1} \bmod p$) are for practical purposes random numbers up to nearly $p$ or $q$, so given the typical values for $p$ and $q$ above, roughly 1/3 of the time these are the same number of bits (1024) and need the extra 00, roughly 2/3 of the time they are 1 to 7 bits smaller and need the same number of octets but no extra 00 or 8 bits smaller and need one less octet for the magnitude plus the 00, and roughly 1/400 of the time they are small enough to need fewer octets.

This rule about an 'extra' 00 applies to both BER and DER, a commonly used subset of BER; see 8.3.2 in X.690. BER gives a choice to include 'redundant' information while DER does not; DER only allows one well defined encoding for a specific type and value combination.

One case where the 00 is typically not included is the public exponent $e$.  The most common value for that is 65537, or 01 00 01 in binary.  The leading bit here is 0, and so a leading 00 byte is not required; hence the typical encoding for this exponent is 02 03 01 00 01.


What is the time requirement for pairing computation and modular exponentiation? I want to design a cryptographic protocol for encrypted search without pairing. I have seen some papers for protocols without pairing. How would I compare pairing computation and modular operations?

I had to do this comparison one year ago in an article, to justify whether it was desirable to avoid pairings in some protocols. Roughly, if you take the (arguably) most efficient up-to-date curves with and without pairing, counting as 1 the cost of a modular exponentiation in the curve without pairing, denoting $\mathbb{G}_1$ and $\mathbb{G}_2$ the (asymmetric) curves with the pairing,

the cost of an exponentiation in $\mathbb{G}_1$ is 3
the cost of an exponentiation in $\mathbb{G}_2$ is 6
the cost of a pairing is 8

For the comparison, we used Bernstein's Curve25519 for the curve without pairing, and  Barreto-Naehrig curves for the curve with pairing (using the implementation of "High-speed software implementation of the optimal Ate pairing over Barreto-Naehrig curves"). Not that the cost of a pairing is not the only thing that matters, as in the best curves without pairing, there are more efficients algorithms for exponentiation than in the best curves with pairings.

Source: https://eprint.iacr.org/2015/246.pdf


Shamir Secret Sharing Modular Reduction Say players use Shamir's secret sharing to share a value $k$ such that each player now holds $k_i$, a share of $k$. How can they securely compute $k \bmod m$ for some $m$.

Of course they can interpolate to get $k$ and then reduce it $\bmod \hspace{2pt} m$. But how can they perform some operation on their shares to obtain shares of $(k \bmod m)$ without revealing $k$?

First note that using MPC we can compute addition, subtraction, multiplication and division (multiplication by the inverse) on shares. It turns out there are also secure protocols out there for doing comparison (see http://viff.dk and their references).

So we could simply do something like this:

while k >= m:
  k = k-m

$m$ could be public or secret shared.

This will be fairly slow if $k$ is large and $m$ is small. As poncho points out, someone learning $k\bmod{m}$ and the number of iterations of the loop will be able to recover $k$.

This could be mitigated by always running the loop the same number of times and using $t= (k>=m)$ (where $t$ takes on $0$ or $1$ accordingly) then doing $k=k-(t)m$. This has obvious limitations so it will depend on the situation as to whether or not this will be acceptable (note that we can upper bound the number of iterations if both $m$ and the order of the field used in Shamir are known).

There are more specialized protocols that would be faster and may solve the problem poncho pointed out.


How would I go about solving this cipher? I am not sure this is the right place to post this... recently I was given the following image by my friend in the context of a game we play together. Please note the characters at the bottom.

I would like to figure out what the characters say, but I am not even sure how I would go about it. I suspect it's some sort of cipher where each symbol represents one specific letter.

What techniques could I use to start trying to figure out what the characters say?

"I suspect it's some sort of cipher where each symbol represents one specific letter."

If your assumption is true then I would recommend frequency analysis, even though this cipher text is rather short.