Tests to distinguish between PRNG and a CSPRNG What are the tests which a regular PRNG would fail but a CSPRNG would succeed? Is it just the next-bit test or are there multiple other tests which a PRNG which is not a CSPRNG would fail? Would a PRNG which is not a CSPRNG pass the Chi Square tests?

What are the tests which a regular PRNG would fail but a CSPRNG would succeed?

The goal of a PRNG, and the duty of a CSPRNG, is to have an output that can't be distinguished from true randomness (with a significant advantage, by a program that can actually be run). Thus it's a failure of a PRNG, and a capital offense for a CSPRNG, if it does not pass all randomness tests it receives (assumed correct and well used, including correctly interpreting the results, which by nature are uncertain to a degree).
Nevertheless, a few bad PRNGs which fail some generic statistical tests like Ent, Diehard, Dieharder, TestU01, NIST SP800-22 rev 1a. More PRNGs fail only specific tests designed with knowledge of the PRNG design.
A well-designed and well-implemented CSPRNG will, by definition, pass all tests. That's including the above list of tests. We can have a (faint) hope that running some tests in this list disprove that a PRNG is a CSPRNG.
Caveat: that's essentially useless to argue (much less, prove) that a PRNG is a CSPRNG (which requires analysis at the design) or well implemented (which require looking at the implementation, and test vectors). Much like analyzing statistics on winning a lottery is not useful to argue that this lottery system is run honestly.
Addition (as rightly suggested by @SEJPM): We can't stress it too much, don't count on generic statistical tests to find weaknesses in PRNGs, or worse CSPRNGs (rather, count on CSPRNGs to help debug statistical tests). A CSPRNGs requires a sound design, and years of analysis, of its design and/or of the primitive(s) it uses, by smart motivated cryptanalysts. Only after they failed to find a theoretical distingisher do we have a serious candidate CSPRNG.

Would a PRNG which is not a CSPRNG pass the Chi Square tests?

That depends on PRNG and test parameters (that might also depend on the seed used). For many non-crypto PRNGs in actual use, and all CSPRNGs, yes. For others, that depends a lot on if the test is run for a long enough sample, and on if the χ2 test is bidirectional or not.

Why do you need to know the PRNG Design?

In cryptography, adversaries are assumed to know everything about the system attacked except the key (that is, for a PRNG, the seed), by Kerckhoffs's principle. They will design clever algorithms, perhaps dedicated hardware (e.g. the bombe), in order to break the system (that is, for a PRNG, distinguish the output from random, or worse predict future output from past output).
And in practice, that makes a helluva of a difference. It's easy to devise a test that predicts the next outputs of MT19937 knowing earlier ≈19968 bits, using a specifically designed test for that generator. Most tests not specifically designed for the class of generators MT19937 belongs to will give its output a clean bill of health.

Why can't the next-bit test be used to distinguish a CSPRNG from a PRNG without knowledge of the PRNG design?

The next bit test is theoretical. Unlike the 5 families of statistical tests I linked to, it's not a program that can be run to completion on a sample of the output(s) of the PRNG tested.
No practical test on the output of a candidate CSPRNG can confirm it's one.


Is it possible to match encrypted documents using user-defined search terms? Suppose I am storing a number of encrypted documents in a database. I would like to make it possible to identify the subset of documents whose contents match user-specified search terms without a) maintaining a plaintext index or b) decrypting documents on the fly. Is there any way to accomplish this securely?

By the same token, I'm wondering if a collection of encrypted documents can be sorted according to an encrypted attribute (e.g., document title) without first decrypting all attribute values.

Yes.  If you encrypt the documents with this purpose in mind (you have to use a special kind of encryption algorithm), then yes, it is possible to do this, for certain kinds of search queries.

There is a rich research literature on this topic.  The buzzword is "search on encrypted data".  I'll point you to a few sample papers in this space.  Do a literature search, and you should be able to find many more for yourself.

CryptDB: Protecting Confidentiality with Encrypted Query Processing, Raluca Ada Popa, Catherine M. S. Redfield, Nickolai Zeldovich, and Hari Balakrishnan.  SOSP 2011.  See also the CryptDB web page.
Secure Indexes, Eu-Jin Goh.
Practical Techniques for Searches on Encrypted Data, Dawn Xiaodong Song, David Wagner, and Adrian Perrig.  IEEE Security & Privacy 2000.
Public key encryption with keyword search, Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano. EUROCRYPT 2004.
Designing Secure Indexes for Encrypted Databases, Erez Shmueli, Ronen Waisenberg, Yuval Elovici, and Ehud Gudes. Database Security 2005.
How to Search on Encrypted Data, Eu-Jin Goh.  Slides.
Private Searching On Streaming Data, Rafail Ostrovsky and William E. Skeith III.  CRYPTO 2005.
New Constructions and Applications for Private Stream Search (Extended Abstract), John Bethencourt, Dawn Song, and Brent Waters.  IEEE Security & Privacy 2006.
Secure Ranked Keyword Search over Encrypted Cloud Data, Cong Wang, Ning Cao, Jin Li, Kui Ren, and Wenjing Lou.  ICDCS 2010.
Enabling Efficient Fuzzy Keyword Search over Encrypted Data in Cloud Computing, Jin Li, Qian Wang, Cong Wang, Ning Cao, Kui Ren, and Wenjing Lou.
New Security Models and Provably-Secure Schemes for Basic Query Support in Outsourced Databases Amanatidis, Boldyreva, O'Neill. 2007
Privacy Preserving Keyword Searches on Remote Encrypted Data Chang and Mitzenmacher. 2005
Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries Cash et al. in CRYPTO 2013
Multi-key Searchable Encryption Popa and Zeldovich. 2013.
Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions Curtmola et al. 2006

The best scheme for your situation will depend upon your application requirements.  If you have a read-mostly database (updates are rarer than searches), then I would suggest a scheme based upon encrypted indexes.  If you need to make modifications frequently, or if searching is relatively rare, the other schemes might be preferable.


What do they mean when saying that a certain value should be “super-logarithmic”? What do they mean when saying that a certain value should be “super-logarithmic”?

I've found the Wikipedia definition of a “super-logarithm”, but I'm having trouble understanding how a given value can be super-logarithmic (in some security parameter).

As for an example of the use of the terminology, see http://research.microsoft.com/en-us/um/people/yael/publications/2010-Symmetric_Encryption.pdf. It appears right in the abstract.

The term super-logarithmic in the paper you cite has nothing to do with the notion of a super-logarithm in Wikipedia. Rather, the intention is simply a function that is asymptotically larger than the $\log$ function. Formally, $f$ is super-logarithmic if $f(n)=\omega(\log n)$. The formal definition of "little-omega" appears in the Wikipedia entry on big-O notation.


Proving the semantic security of the One Time pad Currently hearing a lecture on cryptography, and the professor gave us the definition of semantic security, which is roughly the following (formally not quite complete, but you get the idea):

  Given a function $INFO(1^n,m)$ which determines the information the
  attacker is interested in (e.g. $INFO(1^n,m)=m$ would mean that the
  attacker wants to know the plaintext message $m$) and any
  polynomial-time attacker $A(1^n,C)$ in posession of the cipher text
  $C$, it is possible to construct a Simulator $S(1^n)$ without
  knowledge of the cipher text that has an equal chance of determining
  $INFO(1^n,m)$.

(From reading this stackexchance, it seems like the definition of semantic security that others use here is what was called Indistinguishability (IND) in our lecture. I am not interested in IND, only in semantic security as outlined above)

He then proceeded to talk about how the one-time-pad (OTP) fulfills this requirement, and offered the beginning of a proof. The basic idea of the proof went something like this:

  Given any attacker $A(1^n,C)$, we construct the Simulator $S(1^n)$ in
  the following way: $S$ will pick a random binary string $C \leftarrow \{0,1\}^n$ and then return the result of $A(1^n,C)$. This would mean
  that the chance of $S$ to succeed would be as high as the chance of
  $A$.

Now, to me, that does not make any sense. I mean, it works if you already know that the OTP is secure and that the chance of $A$ to succeed is $2^{-n}$ (for $INFO(1^n,m)=m$), because $S$ also has a chance of $2^{-n}$ to pick the correct binary string. But as we are trying to proove the security, we can't argue that way. And as soon as we can no longer use that knowledge, the proof no longer works in my eyes.

I tried to come up with a proof of the semantic security of the one time pad, and failed so far. I also tried to find an existing proof on the internet, and failed as well. I would have an idea on how to proove indistinguishability, and as far as I know, IND and semantic security are practically equivalent, but I'd be interested in a proof using the above definition.

Any pointers to existing proofs I may have overlooked, or pointers on how I could proove this myself, would be appreciated. Alternatively, an explanation on how the proof the professor outlined could actually work would be appreciated as well. This is not homework, I am doing this because I am interested in the subject matter and because I will go mad if I cannot find a proper proof or an explanation why the proof by the professor works.

The proof for the perfect secrecy property of the one time pad is quite simple.

It makes use of basic probabilities and it says that:
 $$Pr[M=m|C=c]=Pr[M=m]$$ for a probability distribution M$\{0,1\}^n$ for the message space and a probability space C for the ciphertext space.

Proof:

$$Pr[C=c]=\sum{Pr[C=c|M=m']\cdot Pr[M=m']}
=\sum{Pr[K=m'\oplus c]}\cdot Pr[M=m']
=\sum{2^{-n}}\cdot Pr[M=m']
=2^{-n}$$
(from bayes theorem)$$Pr[M=m|C=c] = \frac{Pr[C=c|M=m]\cdot Pr[M=m]}{Pr[C=c]}
= \frac{Pr[k=m \oplus c]\cdot Pr[M=m]}{2^{-n}}
=\frac{2^{-n}\cdot Pr[M=m]}{2^{-n}}
=Pr[M=m]
$$

What the last equation states, is the following:
The success probability of an attacker to correctly guess the plaintext m by inspecting its ciphertext c is equal with the probability of correctly guessing the message without obtaining its ciphertext. The latter argument is the perfect secrecy property.

Perfect secrecy is hard to achieved in real world due to its two constraints:

It's one time: the key should be used only for 1 encryption
The key should be as long as the underlying message

So people started to think:"...hmmm maybe we can weak this security definition in order to be more efficient in practise...". And they end up with the computational semantic security which relaxes the perfect secrecy as follows: No polynomially bounded adversary can with non negligible probability infer any information from the ciphertext. This is the semantic version and the indistinguishable version states that no polynomially bounded adversary can with non negligible probability distinguish two ciphertexts.

In real world the second drawback can be mitigated with the use of pseudorandom generators that very briefly take as input a short "random" looking seed and produce a longer pseudorandom number that is indistinguishable from random. In order to come up with the proof following the reductionist approach for the security of the one-time-real-world pad we substitute the key k with the outputs of a PRG and we make the assumption that PRG outputs are indistinguishable from random. The proof now for its semantic security (which is equivalent with IND security) proceeds as follows:

Assuming that $\mathcal{A}$ breaks the semantic security of our OTRWP attacker $\mathcal{B}$ that tries to break the security of the PRG will use it to break PRG security. If we manage to do so we will end up in a contradiction so the truth statement would be that OTRWP is secure. Let's see how it briefly works:
Whenever $\mathcal{A}$ is asking for encryption of messages m the attacker $\mathcal{B}$:

Gets the output of the PRG when it is fed up with a seed that comes from a uniform distribution.
Gets the output of the PRG when it is fed up with a pseudorandom seed.

We made the assumption that PRG is pseudorandom so the success probability of $\mathcal{B}$ distinguishing between 1 and 2 is negligible:
$Pr[|PRG_{pseudorandom seed}-PRG_{uniform seed}|]=neg(1^k)$
But $Pr[PRG_{pseudorandom seed}]$ is exactly equal the probability of the OTRWP for attacker A and $Pr[PRG_{uniform seed}]=1/2$ because it is independent from the view of $\mathcal{A}$.

So:
$$Pr[\mathcal{A}^{OTRWP}]=neg(1^k)+ 1/2$$
which concludes the proof.


Is a 2 bit one time pad just as secure as a 128 bit one time pad? Obviously, it would be easier to stumble across the answer, but you still couldn't be sure it's correct. So it's still theoretically secure?

Yes, they both satisfy perfect secrecy, but with a 2-bit OTP you can only encrypt a 2-bit message once.


Secretless authentication method for remote hardware We're working with a microcontroller that is not secure enough to store secrets. The ROM could be dumped in a properly equiped lab.

This is why we considered integrating a certified Secure Element that would store the secrets we need for our infrastructure (some keys and certificates). This way the secret would be stored in a valid device regarding security standards.

However, in this new architecture, the Secure Element would be deported from the host microcontroller, which requires to secure the communication between the SE and the Host.

Yet,  all the current authentication methods we know require to store something (a secret, a key a certificate), what we cannot do because the microcontroller is not secure enough...

That leads to two questions:

What is the purpose of integrating a Secure Element or Secure Access Module to address the needs of secret storage for an infrastructure if it requires another secret for connection?
Is there any authentication method that would not require secret, but would garantee anyway identities?

Many thanks

What is the purpose of integrating a Secure Element or Secure Access Module to address the needs of secret storage for an infrastructure if it requires another secret for connection?

One can be quite sure that the genuine Secure Element is involved in a communication that it certifies. If the Secure Element is BGA-mounted and/or epoxy-bounded to a PCB, one can be reasonably confident that this PCB is involved, or that adversaries spent significant effort to workaround that.

  Is there any authentication method that would not require secret, but would guarantee anyway identities?

Not in traditional cryptography, including asymmetric and post-quantum.

Physically Unclonable Functions aim at something close: the PUF is supposed to be impossible to analyse to a degree allowing its successful cloning. One should be reasonably sure that a PUF was involved in a communication that it certifies. If the PUF is integrated on a silicon die, that die was involved too. That's the general idea when the PUF aims at preventing unauthorized production of the die from unmodified photomasks (stolen or reverse-engineered), and/or make the die unclonable.


Why does Shamir's Secret Sharing Scheme need a finite field? I read ampersand's question "Necessity for finite field arithmetic and the prime number p in Shamir's Secret Sharing Scheme", where he asked why Shamir's Secret Sharing Scheme uses arithmetic in a finite field of prime order.

The answers to that question explain that a prime field is not necessary for Shamir's scheme, but, rather, that any finite field can be used.  However, they don't really address the other part of the question, namely why do we need a finite field at all?  Couldn't we just use, say, ordinary integer arithmetic instead?

Can someone please explain (in the simplest possible manner) the reason that Shamir's Secret Sharing Scheme uses finite field arithmetic?

The simplest answer is probably to give an example of information leaked when using Shamir's secret sharing over the integers. Assume that we construct a low degree example, defining $q$ to be a linear polynomial with $q(0)=D$ and $q(1)=a_1$. By interpolation you find that: $$q(x)=(a_1-D)x+D.$$

Assume that you are given the share corresponding to evaluation at $2$, i.e. $q(2)$. You can see that $q(2)=2a_1-D$. Since $a_1$ and $D$ are integers, given this single share, you learn the parity of $D$.


Is there any difference between NIST and SECP curves in-terms of their algorithms and implementation? I'm implementing ECDSA for NIST P-256 curve. I just want to know if the same implementation will also work for SECP curves? If it doesn't, can you point me to one or more references of algorithms for SECP 256?

To clarify: I specifically want to know if there are any differences in algorithms for point addition and point scalar multiplication. For the current NIST implementation I'm using projective coordinates for point addition and multiplication.

Please check https://tools.ietf.org/search/rfc4492 - espessially, the "Appendix A.  Equivalent Curves (Informative)" part.

For example: NIST P-256 is refered to as secp256r1 and prime256v1. Different names, but they are all the same.


What is a trapdoor permutation? Can anyone explain to me what a trapdoor one-way permutation is?  Is RSA a trapdoor one-way permutation?

Context: I was reading about ring signatures.  On page 560, it describes steps to implementing a ring signature. I am confused by step 3, where $g()$ is a trap-door permutation.  The paper briefly says that $g()$ is an RSA trap-door permutation. I thought that RSA was a public-key encryption protocol.  Is RSA a trapdoor permutation?

Read Wikipedia: Trapdoor function

Then read Luca Trevisan's lecture notes (jump straight to section 2. Trapdoor Permutations and Encryption).  Or, read any other textbook or lecture notes that covers trapdoor permutations.

For instance, if $(n,e)$ is a RSA public key, then $f(x) = x^e \bmod n$ is a trapdoor permutation.  It is a permutation, since the function $f:S\to S$ is bijective (where $S=(\mathbb{Z}/n\mathbb{Z})^*$).  It is a trapdoor one-way permutation, since given $x$ and the public key, we can easily compute $f(x)$, but given $y$ and the public key, it is difficult to compute $f^{-1}(y)$; yet with the private key (the trapdoor), we can easily compute $f^{-1}(y)$, given $y$.

That should answer your question.


Is there a problem in a PK cryptosystem if the plaintexts are very small compared to the ciphertexts? I'm wondering, suppose we have a public key cryptosystem $P = (pk,sk)$ such that $$pk: \{0,1\}^n \to \{0,1\}^{n^2},$$ that is, the ciphertexts are $n$ times longer than the plaintexts (here, $n$ is supposed to be the security parameter). My question is

  Does this imply some weakness of any kind on the cryptosystem (as $n$ grows)?

It's not that I have the intuition that there may be an issue, it's just a particular property that makes me think.

BACKGROUND

We're developing a PK cryptosystem based in multivariate polynomial equations. So far, our ciphertexts were as long as our plaintexts, but now we have this situation, where the ciphertext / plaintext length ratio is not constant. This has its own consequences in the algebraic point of view, but in the cryptographic setting... does it have any implication? Thanks!

No.     Also, note that by hybrid encryption, ciphertext overhead will always be

at most   + poly(security_parameter) ,   no matter how long the message is.

For IND-CPA of any

public-key encryption scheme, or even

symmetric encryption scheme with stateless encryption

, ciphertexts for non-empty messages must be

overwhelmingly likely to be longer than plaintexts.

Your most recent comment suggests it was broken even in the following context, but otherwise you might have had a secure trapdoor permutation family whose domains are exactly the binary strings whose length equals the length chosen during key generation.


Which version(s) of SRP are in ISO/IEC 11770-4:2006? I am on the impression that SRP emerges as the least uncommon and best analyzed protocol for authentication and key agreement based on a short password.

This states that SRP is part of IEC 11770-4, among other protocols. But no version is specified, and I've seen there's SRP-1, SRP-2, SRP-3, SRP-6, and the current SRP-6a.

Hence my first question: which version(s) of SRP are in ISO/IEC 11770-4:2006? (link is to a free preview; drafts are available here to those willing to subscribe to a mailing list, and I have yet to spot a meaningful technical difference between the October 31, 2005 draft and the real thing)

Which list of parameters and options to SRP or/and ISO/IEC 11770-4:2006 would be necessary to define implementations to the point of being secure and inter-operable?

Also: ISO/IEC 11770-4:2006 can use an Elliptic Curve setting, with (I guess) shorter cryptograms; is that the case for SRP?

Update: the motivation of the question is that ISO/IEC 11770-4 is an international standard, approved by a committee, which is more reassuring to a decision-maker than SRP-6a as defined by a web page than can disappear or change any second.

In a comment, Smit Johnth suggested TLS-SRP/RFC 5054, which has some traction. That could be a possible choice. I'm reading it as implementing SRP-6a, despite claiming to implement SRP-6 with reference to documents predating SRP-6a. My main reservations are that TLS is a bit heavy for my application; and RFC 5054 is stuck to SHA-1, which is bad from a certification standpoint: in France, any hash less than 200 bits, or 256 bits for use after year 2020, does not match rules in section 2.3 of these official recommendations, which at least can make a prescriber less comfortable.

The multiplier parameter $k$ is different between SRP 6 and 6a. You can see that RFC 5054 calculates it using a hash of the domain parameters (modulus $N$ and generator $g$), so it is using SRP 6a, as opposed to SRP 6 where $k$ is constant.

Likewise, in section 6.2.1 of IEC 11770-4 – the October 2005 draft at least – the equivalent value $c$ is defined as a hash of the domain parameters which it calls $q$ and $g_{q-1}$, so it too is based on SRP 6a.

  Also: ISO/IEC 11770-4:2006 can use an Elliptic Curve setting, with (I guess) shorter cryptograms; is that the case for SRP?

Yes. The protocol in 6.2 is defined for either of the fields in section 5: the discrete logarithm one or the elliptic curve one.


What are the vulnerabilities of this OTP-like system? I've read that a OTP is only perfectly secure if the key is perfectly random, and the pad is never reused.

If you encrypt documents using two keys, where one is random but stays constant for some period of time, and the other is only pseudo-random but unique to each message, is the security of the OTP better or worse than if you used only one key or the other?

And would it still be vulnerable to frequency analysis?

I've read that a OTP is only perfectly secure if the key is perfectly random, and the pad is never reused.

But you've left out the most important condition: the key space must be as large as the message space.

  If you encrypt documents using two keys, where one is random but stays constant for some period of time, and the other is only pseudo-random but unique to each message, is the security of the OTP better or worse than if you used only one key or the other?

You don't specify how the keys are used to encrypt documents, but since you've been talking about one-time pads I will assume the keys are as long as the documents and the encryption works by XOR.

Encrypting messages with distinct pseudorandom key streams is called a stream cipher, and is already secure if the pseudorandom stream generator used is secure and the same keystream is not used twice.  So we can refactor your idea into two components, applied in sequence:

Encrypt the documents with a stream cipher, applying a different keystream to each document;
XOR each ciphertext with a the same true random long-term key.

This has to be at least as secure as the stream cipher is; even if the adversary knows the long-term key for step #2, they'd still have to break the stream cipher.
 This is theoretically less secure than the OTP's "perfect security," but can be plenty secure in practice; my browser session to this site, for example, is protected by such a stream cipher.

Now, the question is whether the addition of the reused long-term true random key enhances the security in any way.  The answer is no, because an adversary who can break the stream cipher is able to exploit the reuse of the long-term key to break the composite system.  Notating the long-term key as $K_L$, the pseudorandom key streams as $K_1, K_2$, the plaintexts as $P_1, P_2$ and the ciphertexts as $C_1, C_2$, the encryptions satisfy these equations (where $\oplus$ is bitwise XOR):

$$
\begin{align}
C_1 &= P_1 \oplus K_1 \oplus K_L \\
C_2 &= P_2 \oplus K_2 \oplus K_L
\end{align}
$$

Solving both equations for $K_L$:

$$
\begin{align}
K_L &= P_1 \oplus K_1 \oplus C_1 \\
K_L &= P_2 \oplus K_2 \oplus C_2
\end{align}
$$

By transitivity of equality:

$$
\begin{align}
P_1 \oplus K_1 \oplus C_1 &= P_2 \oplus K_2 \oplus C_2
\end{align}
$$

And now I can solve for the XOR of the two plaintexts:

$$
\begin{align}
P_1 \oplus P_2 &= K_1 \oplus C_1 \oplus K_2 \oplus C_2
\end{align}
$$

This is significant, because obtaining the XOR of two plaintexts is the basis for the standard two-time pad attacks:

How does one attack a two-time pad (i.e. one time pad with key reuse)?
Many time pad attack
http://www.juliansanchez.com/2012/07/06/a-friday-puzzler-un-xoring-two-plaintexts/

$K_1$ and $K_2$ are pseudorandom keystreams, I can use a brute force attack to enumerate possible values for them, and use statistics on the implied values $P_1 \oplus P_2$ to infer whether I've hit the right key.  And then when I've found the value $P_1 \oplus P_2$, I can try the two-time pad attacks on it.

So your proposal's security is more or less the same as just using the stream cipher.  Lesson: just use the stream cipher.


Why are leaf nodes hashed in merkle tree? I was reading the following on Wikipedia, it appears that the leaf nodes are hashed. What are the benefits of this? Why is it done?. I fell like they are done so that they can be transferred securely. However, I am not sure about this, would like some points to resources

Merkle Tree is based on hashing to the root to provide an efficient digital signature. If the leaves just contain a single data then the parents cannot contain the hash of both children and the combined hash in a simple node design. This can complicate the structure and programming so that the last parents must contain the hash of their children and their combined hashes, too.
You can design like that, however, it will not simple as the Merkle tree. For example, as pointed on the patent, you can design a Merkle tree  trinary tree too.
This is rather an efficiency issue, not a security issue if the hash chain still has the countermeasure to prevent the second pre-image attack with the prefixes.


Real world example of non-interactive zero knowledge proofs? I am very interested in finding out more about the non-interactive zero knowledge proofs after reading the simplified and abstract examples about zero knowledge proofs themselves here.

For the NI-ZK, most answers over here are either very technical or on a very generic level that i have a hard time understanding it.

I do understand the concept for using NI-ZK with a common shared string (CRS): Instead of having a challenge from the Verifier, the Prover simulates it. But the CRS is completely known to the Prover and he can look at the consequence of possible commitments, refraining from them if he may be wrong, can't he? If i use the example on wikipedia for ZK proofs:

  In this story, Peggy has uncovered the secret word used to open a
  magic door in a cave. The cave is shaped like a ring, with the
  entrance on one side and the magic door blocking the opposite side.
  Victor wants to know whether Peggy knows the secret word; but Peggy,
  being a very private person, does not want to reveal her knowledge
  (the secret word) to Victor or to reveal the fact of her knowledge to
  the world in general.

  They label the left and right paths from the entrance A and B. First,
  Victor waits outside the cave as Peggy goes in. Peggy takes either
  path A or B; Victor is not allowed to see which path she takes. Then,
  Victor enters the cave and shouts the name of the path he wants her to
  use to return, either A or B, chosen at random. Providing she really
  does know the magic word, this is easy: she opens the door, if
  necessary, and returns along the desired path.

Now if we replace Victor with a CRS, Peggy would f.e. enter at entry A and look at a position that is the equivalent of her decision (or where would she look?) whether she should leave the cave at A or B, in this case B. But why doesnt she just look it up beforehand? She has the CRS and she knows where she would have to look at if she took either sides - she can just see that if she goes to A first, she is supposed to come out at B. So instead of really committing to A, she secretly sneaks into B and gets out there without having to pass the magic gate.

The argument about Peggy being able to start over is not about NI-ZK proofs, it is about zero knowledge in general.

Zero knowledge does not give you a definite certainty that Peggy actally has the claimed knowledge. In your example, the probability of Peggy being able to cheat is $1/2$ after one round. If we do this for two rounds, the probability that she cheated twice succssfully is $1/4$. This goes on, until there is a satisfying probability, e.g. that Peggy could only cheat with probability of $1/2^{80}$ for 80 rounds.

Now, if we require in a NI-ZK proof that Peggy created a transcript with 80 rounds, she would have to start over for $2^{80}$ times to find such a transcript, if she doesn't have the ability to go back just one round. This has to be enforced, which is done in the Fiat Shamir heuristic by hashing all the previous results. In the CRS model this is achieved by defining the reference string only with a certain distribution and granting no one authority over this choice. This assumption implies, that Peggy can not just go back one step. If she starts over from the beginning, the entire string would change.

From a practical point of view, this is a challenge. The most commonly suggested practical solution would be a trusted third part, like for certificate authorities. But the effort of creating and publishing common reference strings is quite a lot more complex than building a PKI.

For some interesting arguments about this, and a possibly different realization I would suggest reading Cryptography in the Multi-string Model by Groth and Ostrovsky. Especially the introduction is quite interesting and their proposed new setup assumption.

Considering most usages of a CRS in the sense of NI-ZK is that there is usually some property, which is then used in order to prove the ZK property. In regular ZK you give the simulator some kind of advantage, e.g. being able to rewind one step. In this model you use some kind of commitments, which are binding in the real protocol but the advantage of the simulator is that he can decomit his previous commitsments to anything.


SSH sequence number validity? Looking at RFC4253, I came across the notion that the MAC is applied the encoded packet concatenated with a sequence number which acts as a counter.

However, I couldn't find any information on how that sequence number is validated. What happens if some messages get dropped or corrupted during transit?

Also, when do SSH connections get dropped? As in, decryption failure, MAC verification failure, etc.

However, I couldn't find any information on how that sequence number is validated. What happens if some messages get dropped or corrupted during transit?

SSH, similar to TLS, assumes that it is running over a reliable [1] transport protocol (such as TCP).  If something goes wrong (e.g. some message is corrupted or dropped), then the system assumes that the system is under attack, and the connection is dropped.

This is explicitly stated in section 9.3.5 of RFC4251, which states:

This protocol is designed to be used over a reliable transport.  If
transmission errors or message manipulation occur, the connection is
closed.  The connection SHOULD be re-established if this occurs.

[1]: By reliable transport, I (as well as the RFC) mean that it delivers bytes correctly and in order, assuming that the system is not under attack.


Why was WEP apparently not reviewed by many cryptographers? According to this analysis of WEP,

  These attacks point to the importance of inviting public review from people with expertise in cryptographic protocol design; had this been done, the problems stated here would have surely been avoided.

It is my understanding that the design flaws of WEP were well known from its beginning. In WEP’s design process, why were no people with sufficient “expertise in cryptographic protocol design” involved in the creation of a cryptographic protocol intended for broad adoption?

It is my understanding that the design flaws of WEP were well known from its beginning.

WEP on Wikipedia states, was introduced in IEEE 802.11 in 1997, and it was based on the stream cipher RC4.

There has been quite a lot of research to break WEP and its stream cipher RC4, but that's spread out over the last 20 years. Most notably for breaking WEP was the attack from Fluhrer, Mantin and Shamir in 2001. And earlier in 2001, this work was presented at a workshop and a conference (thanks @poncho for this reference).

For RC4, it was public knowledge that it is distinguishable from random, as pointed out by @SqueamishOssifrage in this source. Today that would surely disqualify the streamcipher to be considered secure, but mindsets change over time and I don't know if that was acceptable or not. E.g. the linked source states: "If your application can't stand a bias of 1 part per million, then
don't use RC4." Also, we do not know whether the people in charge of WEP were aware of this or not.

So no, your statement is wrong. Just because the flaws are well known today does not mean they were back then. If you're questioning decisions, you need to adapt the point of view from the time of that decision.

  In WEP’s design process, why were no people with sufficient “expertise in cryptographic protocol design” involved in the creation of a cryptographic protocol intended for broad adoption?

This can't be answered properly, unless you ask someone who actually was involved in that process. The only suggestion I have would be to contact the  IEEE 802.11 working group and ask them.


Why use an Initialization Vector (IV)? Why use an Initialization Vector (IV)?

How are IV's used?
What are the advantages/disadvantages of using an IV?
Why use an IV instead of a longer key in which some section of the key is public?
What happens to various security properties if an IV is insufficiently random?
Are IV's always public knowledge? If so is this the property that distinguishes an IV from a Key?
Given that IV are often public are there any attacks that involve a man-in-the-middle attack that alters the IV?

Many cryptographic algorithms are expressed as iterative algorithms. E.g., when encrypting a message with a block cipher in CBC mode, each message "block" is first XORed with the previous encrypted block, and the result of the XOR is then encrypted. The first block has no "previous block" hence we must supply a conventional alternate "zero-th block" which we call "initialization vector". Generally speaking, an IV is whatever piece of data is needed to begin running an algorithm, and is not secret (if it was secret, we would call it a "key", not an IV).

If you take a look at MD5, you see that it is an iterative algorithm which has a "running state" (four 32-bit words) and processes message data by 64-byte chunks, each yielding the next running state; the final state is the hash output. This has to begin with a conventional initial state, which is described in section 3.3 of the RFC.

Since an IV has some cost (e.g. it must be transmitted along a message), it is not there just for aesthetic reasons: algorithms which use an IV need it to fulfil some sort of security property, and this may imply some constraints on what value an IV may have. This really depends on the algorithm. For instance, with MD5, the IV is fixed and this is not an issue. For the case of CBC, see this answer to a previous question. Since uniform randomness is a difficult requirement (alea is a scarce resource, especially in embedded systems), it is considered a good thing if an encryption algorithm requires only a non-repeating IV (e.g. a simple counter); this is all that newer encryption modes such as EAX need.

An IV can be made public but nothing forces you to. It still tends to have a lifecycle distinct from that of a key, in that (for symmetric encryption) you need a new IV per message but not necessarily a new key. For instance, with TLS 1.2, a session key is created during the tunnel setup (the "handshake"), then data is encrypted as so many "records" (up to 16 kB of data per record) and each record has its own IV.


What is the link between the parity check matrix, double-error-correcting codes and APN permutations? I am currently reading a research paper (linked below) which mentions that a map $f:V:=GF(2^{m}) \rightarrow V$ which vanishes at 0 is APN if it satisfies the condition that it is a binary code $C_{f}$ with parity check matrix
$H_{f} =
\begin{bmatrix}
\dots & \omega^{j} & \dots \\
\dots & f(\omega^{j}) & \dots
\end{bmatrix}$
that is double-error-correcting (i.e. no fewer than 5 columns sum to 0).

From other sources that I found double-error-correcting also means that the minimum distance of the code should be 5.

However, I do not understand how all these definitions tie in together. Specifically, I do not understand how "no fewer than 5 columns sum to 0" ties in with the minimum distance of the code should be 5". Further, it would be great if anyone could clarify what "minimum distance 5" means.

An APN Permutation in Dimension 6

This quite technical connection was ultimately proved in the paper

  C. Carlet, P. Charpin and V. Zinoviev. Codes, bent functions and permutations suitable for DES-like cryptosystems. Designs, Codes and Cryptography 15(2), pp. 125–156, 1998.

See also the paper by the same authors plus Dobbertin in the IEEE Transactions on Information Theory, around the same time. I'll give an executive summary in its classical form without all the equivalences discovered later.

In pseudorandom sequence design, the Gold Sequences have the form
$$
g_t=T(a z^t)+ T(z^{(2^k+1)t}), \quad t\geq 0
$$
where $T$ is the trace map from $\mathbb{F}_{2^n}$ to $\mathbb{F}_{2},$ $z$ is a primitive element in $\mathbb{F}_{2^n}$ and $gcd(n,k)=1.$

The sequence $T(az^t)$ is generated by a primitive LFSR corresponding to the characteristic polynomial $M_z(x)$ of $z$ and has period $2^n-1.$ The sequence $g_t$ is a sum of this sequence with its decimation by $2^k+1.$

Sequences taken with all their shifts form cyclic codes.

The Gold sequences viewed as a cyclic code in classical form have $k=1$, thus they are generated by the product $M_z(x)M_{z^3}(x).$

This means that the zeroes of this code are the union of those of $M_z$
$$
\{z,z^2,z^4,\ldots z^{2^{n-1}}\},
$$
and of $M_{z^3}:$
$$
\{z^3,z^6,z^{12},\ldots z^{3\cdot 2^{n-1}}\},
$$
thus have the 4 consecutive zeroes $\{z,z^2,z^3,z^4\}$ giving a cyclic BCH code of minimum distance $d=4+1=5.$


Transforming SHA-512 into SHA-512/256? Based on my skimming over FIPS 180-4 it looks like the only difference between SHA-512 and SHA-512/256 is the initial hash value and the fact that the final output is truncated to 256 bits.

My question is:  if you have a library that does SHA-512 can you transform that to SHA-512/256?

Like maybe there could be some sort of magic string that, when prepended to the original message, makes the first 256 bytes of the SHA-512 hash of the original message the same as SHA-512/256? Or maybe you could xor the first x bytes of the original message with some magic string?

I'm guessing that there isn't such a way but I thought I'd ask all the same.

Like Richie Frame commented, as SHA-2 padding uses the length of the message that is not possible. Specifically, even if you had some string of input that took you from the SHA-512 IV to the SHA-512/256 IV, any message you hashed with it prepended would have a different length and thus a different hash value.

Additionally, even ignoring the padding it would be infeasible to find such a string. The IV constants for SHA-512/n have been chosen using an algorithm that does not start with the normal SHA-512 IV, so it would require a preimage attack on the compression function to find one.

However, unless you need compatibility or conformance with SHA-512/256, you could just use SHA-512 and truncate. See page 27 of the FIPS document you linked.


Attacks on one-time pad, given a property of keys An adversary $A$, eavesdrops $n$ cipher-texts, $c_{1}, c_{2} ..., c{_n}$. It also knows a value $v$ and a function $f$ such that $$f(k_{1}, k_{2}, ..., k_{n}) = v$$ where, $k_{i}$ is used to encrypt $m_{i}$ to obtain $c_{i}$, $\forall i| 1\leqslant i\leqslant n $.

As a concrete example say, $A$ listens to three cipher texts, $c_{1}, c_{2} \text{ and } c_{3}$, and knows that $k_{1} \oplus\ k_{2} \oplus\ k_{3} = 1^l $, where cipher $c$, message $m$ and key $k$ are of the same bit length $l$.

In the concrete case, how could $A$ use this information in guessing $m_{1}, m_{2} \text{ and } m_{3}$ ? In the general case, are there any well known methods that I should be aware of? Where can I learn about such general techniques in detail?

Assume, messages are drawn uniformly at random (frequency analysis is not possible).

Let's first look at the concrete case;

We already know that when a key is used more than once, one-time pad becomes insecure with this two questions and nice answers on crib-dragging.

How does one attack a two-time pad (i.e. one-time pad with key reuse)?
How to attack a “many-time pad” based on what happens when an ASCII space is XORed with a letter?

But, in your case the keys are not the same, only a relation is given by

$$k_1 \oplus \ldots \oplus k_n = 1^l $$ (message length $n$ and number of keys confuse here let $l$ be the message length)

now, let $n=2$ messages $m_1$ and $m_2$ than $k_1 \oplus k_2 \oplus 1^l $

If we x-or the two ciphertexts $c_1$ and $c_2$ of $m_1$ and $m_2$, respetively;
$$ c_1 \oplus  c_2 = m_1 \oplus k_1 \oplus m_2 \oplus k_2 = m_1 \oplus m_2 \oplus 1^l$$
then;

$$c_1 \oplus  c_2 \oplus 1^l = m_1 \oplus m_2 $$ So the solution for this is nothing but the usual two-time pad.
now let we $n=3$ messages $m_1, m_2$ and $m_3$ than $k_1 \oplus k_2 \oplus k_3 \oplus 1^l $. than we will have
$$c_1 \oplus  c_2 \oplus c_3 \oplus 1^l = m_1 \oplus m_2 \oplus m_3$$

This can be also attacked but will be harder, since we have to guess two words and see that it reveals from the third message. The expected time is the square of the $n=2$ case for the initial guesses.
When $n$ becomes bigger it will require more guess and trials.

Arbitrary $f$

Here, let's look only the case $n=2$, and only ideas;

We have $c_1 = m_1 \oplus k_1$, $c_2 = m_2 \oplus k_2$, and $f(k_1, k_2) = v$

We can't apply crib-dragging here since

$$ c_1 \oplus c_2 = (m_1 \oplus m_2) \oplus (k_1 \oplus k_2)$$ guessing $m_1$ will not give any information. An attack can be performed by guessing two words and verifying that $k_1$ and $k_2$ satisfies two relations;

$$k_1 \oplus k_2 = m_1 \oplus m_2 \text{ and } f(k_1, k_2) = v$$


Are "deterrent" algorithms like NFS and Coppersmith's algorithm actually used in practice? It seems like there are a lot of algorithms in number theory which I would classify as "deterrent" algorithms -- for example the various number field sieves for factoring, Coppersmith's algorithm for discrete logarithm -- which effectively serve as a benchmark for the cost of attacking a cryptographic protocol. They have immense value to society by justifying minimum bit sizes needed to make attacks intractable.

But I wonder: do these algorithms actually get used on a regular basis? After all, if there are systems that can be successfully attacked by these
algorithms, then those systems are not properly designed.

Technically, yes.

The number field sieve was used to break a 768-bit RSA challenge.

What is probably the current best effort (unclear whether it's still ongoing) to break a 130-bit elliptic curve challenge uses Pollard's rho algorithm.

Wikipedia lists many more references.

I say ‘technically’, of course, because these aren't ‘attacks’ on real systems; they are attacks on challenges to demonstrate the cost of the attack by academics who get to win grant funding in exchange for performing it, which we hope is a good proxy for the cost to real attackers.  It is exceedingly unlikely that these academics would intentionally attack real systems, too, because the ethical issues are more obvious than the back door in Dual_EC_DRBG, and nobody else who might carry them out is motivated to disclose their cryptanalytic capabilities.

I would guess that well-funded intelligence agencies such as the NSA devote some resources to NFS, Pollard's rho, etc., for stupidly small parameter choices made by people who don't know any better, or by people who should have known better but were under the influence of the selfsame state intelligence agencies, or in historical systems—such as major internet protocols that were designed when US crypto export controls were in effect.

But mostly they probably spend effort on working around the crypto rather than breaking it, since on a scale from one to ten of sturdiness, modern cryptography rates somewhere around a nine and most modern so-called software ‘engineering’ rates somewhere negative.


Is it possible to acquire the next keystream of Salsa20? (If you know part of the keystream) When you know the Salsa20's keystream, how do you know the next keystream?
In other words, can I infer the next keystream when I don't know the Key and IV of Salsa20, but the keystream is 0x100000?
If you have any related attack papers, please recommend it.
Or, I'd like to ask for some search keywords.

It is impossible for computationally bounded adversaries
What you are looking for is impossible in modern stream ciphers. If ever one finds to break a stream cipher in this way, you will see in the cryptographic news!

but the keystream is 0x100000?

First of all, the keystream is too small to extract the key and IV, even there is an attack. There is a lot of occurrence of this keystream on the period of the Salsa20's keystream but you cannot reach them in your lifetime.
The expected period of Salsa20 (Oversimplified!):
The Salsa20's core function maps a 256-bit key, a 64-bit nonce, and a 64-bit counter to a 512-bit block of the keystream. So we have 384-bit random input and 512-bit output. If we assume that the output of the Salsa20 is a pseudo-random sequence with an output size of $n=512$-bit the expected period length will be  $\sum_{i=1}^n i/n = (n + 1)/2 \approx 2^{511}$ with the Harris' 1960 work. Salsa20, however, limited with the counter 64-bit. So can simply say that, a key with a nonce will not be periodic.
What is the expected occurrence on a pseudo-random sequence of size $2^{64}$? It is $2^{64}/2^{24} = 2^{40}$. So, for a single (key,nonce) pair, there is around $2^{40}$ occurrence of your string randomly sitting somewhere on the keystream. What is the following as the next bit? Nobody knows. For how many (key,nonce) pair you can store this to attack? And how you will be lucky that your target will be hot on your tiny list?
The next-bit test
This is more formal in the The next-bit test;

In cryptography and the theory of computation, the next-bit test is a test against pseudo-random number generators. We say that a sequence of bits passes the next bit test for at any position $i$ in the sequence, if any attacker who knows the $i$ first bits (but not the seed) cannot predict the $(i+1)$st with reasonable computational power.

If one computationally bounded entity can predict the next bit from the given bits, then this is a big problem for any stream cipher. There is no known such attack on Salsa20.
And, note that next-bit test is not sufficient, a non-Pseudo-Random-Sequence can pass the test.
Attacks on Salsa20
The best attack on the Salsa20

in 2008, New Features of Latin Dances (PDF) by Aumasson at al. They have shown 8 round attack on Salsa20/12 and 12 round on full Salsa20/20;

The other attacks;

in 2005, The paper Truncated differential cryptanalysis of five rounds of Salsa20 by Paul Crowley won Bernstein's US$1000 prize for "most interesting Salsa20 cryptanalysis"

in 2006, Fischer et al. in the paper Non-randomness in eSTREAM Candidates Salsa20 and TSC-4 demonstrated an attack on Salsa20/6 with estimated time complexity  $\approx 2^{177}$. They also showed a  related-key attack on Salsa20/7 with estimated time complexity $\approx 2^{217}$. The related key attacks are not important for the encryption, since the keys are selected randomly, it is important when uses in hash constructions.

in 2007, there is an attack on 8 rounds of Salsa20 in the paper Differential Cryptanalysis of Salsa20/8 by Tsunoo et al. This attack has no improvement over the brute force since they have $2^{255}$ complexity. In the same paper, they have also shown a related-key attack on the 7 rounds of the Salsa20 with $2^{117}$ complexity.

in 2012, Shi et al. improved the attack of Aumasson et al. on the paper
Improved Key Recovery Attacks on Reduced-Round Salsa20 and ChaCha. Note that the improvement is on 128-bit keyed Salsa20/7 with $2^{109}$ complexity time and on 256-bit keyed Salsa20/8 with complexity $2^{250}$.

in 2013, Mouha and Preneel gave proof on differential cryptanalysis. Towards Finding Optimal Differential Characteristics for ARX: Application to Salsa20. They showed that 15 rounds of Salsa20 are 128-bit secure against differential cryptanalysis. Their work proved that Salsa20 has no differential characteristic with higher probability than $2^{130}$, as a result, the differential cryptanalysis would be more difficult than 128-bit key exhaustive key search.

in 2018, it is shown that the Salsa20 has no integral distinguisher after 6 rounds, Finding Integral Distinguishers with Ease by Eskandari et al.

in 2020, Improved Related-Cipher Attack on Salsa20 Stream Cipher by Lin Ding. They demonstrated an attack on the use of two different IVs on the same key for Salsa20/12 and Salsa20/8 They can recover the 256-bit secret key with time complexity of about $2^{193.58}$. This is an improvement on the existing attack by a factor of $2^{30.42}$ This seems the best-realated cipher attack.


RSA: finding e given n, m and c So I'm not sure if this is possible but assume I have

$$c \equiv m^e \pmod n$$

I have $c$, $m$ and $n$ but no $e$, which in my case I a value that can be up to 15 digits. Is there a way to do this?

As SEJPM suggested, it's quite practical for the range of $e$ in question.

Here's an easier way than the Kangaroo method:

Set $\lambda \approx. 10^{7.5}$; the exact value isn't important, but the below works most efficiently if the approximation is close.
Compute $A_i = c m^i \bmod n$ for $i = 0 .. \lambda - 1$ using about $ \lambda$ modular multiplies
Store all the $A_i$ values in a fast lookup table (e.g. a hash table)
Compute $z = m^\lambda \bmod n$
For $j = 1 .. 10^{15} /\lambda$ compute $B_j = z^j \bmod n$, and check if the value $B_j$ appears anywhere in the $A_i$ list.

If we have $B_j = A_i$, then we know that $e = \lambda j - i$

Assuming $e$ is in the range $0 .. 10^{15}$, this will always find it, using about $2 \lambda$ modular multiplies; quite doable on a standard PC.


Find ECDSA PrivKey to PubKey = 0 I know it should be impossible (or at least infeasible hard) to extract a ECDSA Private Key from a given Public Key (discrete logarithm problem). But I'm not deep enough into ECC to find an answer to this question:
is it possible/easier to find the private key if the corresponding public key is Zero? (like "0x000...000")?
Of course the curve details (base point, finite field etc) is given too.

Thanks alot!

Yes, actually it is rather trivial.

First we need to dive a little bit into how elliptic curves work. Take a finite field, usually $\mathbb F_p$ for some fixed prime $p$. We call the set of all pairs $(x,y)\in\mathbb F_p^2$ satisfying the equation $y^2\equiv x^3+ax+b\pmod p$ the elliptic curve $E_{a,b}(\mathbb F_p)$.

First we note that $(0,0)$ is on the curve if and only if $b=0$. However, for practically used curves this is not the case. So we can conclude that your request doesn't actually ask for the point which gets encoded to $(0,0)$ (because it isn't on any curve) but rather for the semantic point $0$ that fullfills the same role as the $0$ for the integers, the rationals, the reals, that is the role of the additive neutral element in a group. The encoding of $\mathcal O$ as all-0x00 bytes is confirmed in SEC 1 v2 section 2.3.3 (PDF).

Now we commonly write the points on an elliptic curves as a group, because we can add them, we can subtract them, they have a neutral element $\mathcal O$ ("the point at infinity") and addition is associative.

Now that we have made use of 3 of the 7 usual parameters for elliptic curves, let's look at the rest. Two parameters encode the base point, that is a point $G=(g_x,g_y)$ on the curve which is fixed and used as the reference element for all cryptographic operations. In fact the private key $d$ to your public key point $Q$ has to satisfy the relation $Q=[d]G$, that is addition of $G$, $d$-times with itself yields $Q$.

So now for the last two parameters. Remember when we talked about the curve being the set of all points? It turns out that we actually need to know how many there are. This is called the order of the curve and is not encoded usually in the domain parameters. However, the order of $n$ of the base-point is encoded and that is precisely the integer such that $\mathcal O=[n]G$, so the "private key" to "0x0000...000" is actually directly encoded in the domain parameters.

To satisfy the curiosity you surely have: The last value encoded is the co-factor, that is the quotient of the curve's order and the base-point's order, we need this for some computations.

If you are now asking yourself, whether $n$ is the private key, then the answer is "no". It is the private key that is smaller or equal to $n$ and larger than $0$, however, any multiple of $n$ will work. That is $d'=2n$ will work just the same as $d''=3n$, because in this setting they designate the same as all scalar factors are reduced $\bmod n$ and $0\equiv n\equiv 2n\equiv 3n\equiv\ldots\pmod n$.

On a final note (as pointed out by @fgrieu in the comments): No sane implementation would accept $\mathcal O$ as a public key (section 3.2.2.1 of SEC 1 v2 (PDF)), because it would offer no security as discussed above. On key generation there's also the standard restriction that $0<d<n$, meaning no sane implementation would ever generate $\mathcal O$ as the public key (section 3.2.1 of SEC 1 v2 (PDF)).


The effect of truncated hash on entropy Suppose I have a 128-bit random binary string (128 bits of entropy), then I hash it using SHA-256, then I take the first 128 bits of the output hash. Does the taken bit string still have (almost) 128 bits of entropy or the entropy is reduced to 64 bits? (I mean another 64 bits of entropy probably lies in the second 128 bits of the output hash).

I am confused because in the definitions of cryptographic hash functions that I have read in the past it was said that if one bit of input is changed then every bit of the output changes with a probability of $1/2$. It seems from this we can deduce that our truncated output still has (almost*) the same entropy as the input. Is that right?

*: I added 'almost' to mean ignoring the possible hash collisions.

Expected entropy in the output of a random oracle

The expected entropy in the output of a $h$-bit random oracle fed with random $h$-bit input is close to $h-0.8272$ bit, for even moderate $h$ (e.g. at least $32$). As $h$ grows, that expected entropy becomes arbitrary close to $h-\eta$ bit with
$$\begin{align}\eta&=\frac 1{e\ln(2)}\sum_{i=1}^\infty\frac{\ln(i+1)}{i!}\\
&=0.82724538915300508343173\dots\text{bit}\end{align}$$
where the sum is given by A193424.

Proof, where I'll be using $a\approx b$ as a convenient shorthand for $\displaystyle\lim_{h\to\infty}\frac a b\ =\ 1$

For a particular distribution implemented by the oracle, let $n_j$ be the number of output values appearing exactly $j$ times among the outputs for all inputs. The exact entropy $H$ for that particular distribution can be computed from the $n_j$ by applying the definition of entropy, giving
$$\begin{align}H&=\sum_{j=1}^{2^h}n_j\;\frac j {2^h}\;\log_2\left(\frac{2^h}j\right)\\
&=\frac h{2^h}\sum_{j=1}^{2^h}j\;n_j\;-\frac 1{2^h}\sum_{j=1}^{2^h}n_j\;j\;\log_2(j)\end{align}$$
where we have (by merely counting what all inputs lead to)
$$\sum_{j=1}^{2^h}j\;n_j\;=2^h$$
thus
$$h-H=\frac 1{2^h}\sum_{j=1}^{2^h}n_j\;j\;\log_2(j)$$
For fixed $j$ and as $h$ grows, by counting of the possibilities, we can establish that for random distribution, odds that any particular value is reached $j$ times is $\displaystyle\approx\frac 1{e\;j!}$. Thus for fixed $j$ and as $h$ grows, the expected $n_j$ is $\displaystyle\approx\frac{2^h}{e\;j!}$.
In the exact expression of $h-H$, all the terms in the sum are non-negative. To obtain an asymptotic of the expected $h-H$ when $h$ grows, we can thus replace $n_j$ by its expected value, and obtain that when $h$ grows the expected value of $h-H$ is $\displaystyle\approx\frac 1 e\sum_{j=1}^\infty\frac{j\;\log_2(j)}{j!}$.
The stated result follows by defining $i=j-1$, and removing the sum's first term, which is zero.

I've been unable to locate a source; the closest I found is an empirical derivation of $\eta$ to 4 decimals by Andrea Röck: Collision Attacks based on the Entropy Loss caused by Random Functions, WEWoRC 2007, slides; with more in her thesis.

My first empirical derivation was using a program which draws $2^h$ pseudo-random $h$-bit values and counts how many values are reached how many times; for $h=35$ (the largest I could do with 20GB RAM), three runs gave:

             run 1                run 2                run 3
  0  12640123427 36.79%   12640183855 36.79%   12640308584 36.79%
  1  12640408212 36.79%   12640365800 36.79%   12640104651 36.79%
  2   6320124091 18.39%    6320013534 18.39%    6320174710 18.39%
  3   2106681541  6.13%    2106762262  6.13%    2106726749  6.13%
  4    526645276  1.53%     526674914  1.53%     526679947  1.53%
  5    105334156  0.31%     105325000  0.31%     105330269  0.31%
  6     17561277  0.05%      17551924  0.05%      17556150  0.05%
  7      2507918  0.01%       2508727  0.01%       2505282  0.01%
  8       313971  0.00%        313943  0.00%        313406  0.00%
  9        34748  0.00%         34553  0.00%         34755  0.00%
 10         3424  0.00%          3542  0.00%          3546  0.00%
 11          291  0.00%           287  0.00%           292  0.00%
 12           31  0.00%            24  0.00%            24  0.00%
 13            4  0.00%             3  0.00%             2  0.00%
 14            1  0.00%             0  0.00%             1  0.00%
 15+           0  0.00%             0  0.00%             0  0.00%
entropy   34.172763 bit        34.172758 bit        34.172751 bit

Application to the question: the entropy for the output of SHA-256 truncated to its first $128$ bits when fed a random $128$-bit input is about $127.173$ bit, down from very close to $128$ bit before truncation (see final note). The truncation does not halve the entropy, because the halves are not independent. The right line of thought is that SHA-256 truncated to its first $128$ bits is a fine $128$-bit hash, and behaves like a random oracle.

Note: if we consider a random function from $\{0,1\}^{128}$ to $\{0,1\}^{256}$, most likely there is a small $k$ (most often $0$ or $1$, sometime $2$, rarely $3$ or more) such that $k$ outputs have exactly two corresponding inputs, $2^{128}-2k$ outputs have exactly one, and $2^{256}-2^{128}+2k$ outputs have none (odds that any output is reached three or more times are negligible).

Therefore, in this most likely case, the entropy on output of that function when fed a random $128$-bit input is $-k\;2^{-127}\log_2(2^{-127})-(2^{128}-2k)\;2^{-128}\log_2(2^{-128})$, that is $128-k\;2^{-127}$.

The best model we have for SHA-256 (not truncated) for $128$-bit input is a particular function chosen at random among functions from $\{0,1\}^{128}$ to $\{0,1\}^{256}$, thus we can conclude the entropy for the output of SHA-256 when fed a random $128$-bit input is likely exactly $128-k\;2^{-127}$ for $k\in\{0,1,2\}$, which is very nearly $128$ bit, down to about the 37th decimal places.


Affine Cipher - Pair of plain to cipher text Consider an affine cipher.

  The cryptanalyst observed the following plaintext/ciphertext pairs $(p,c)$: $(8,15)$ and $(5,16)$.

  Recover the key $(a,b)$ used in the encryption system above.
  What is the ciphertext corresponding to the plaintext $p=3$?

For #1, I came to this result:

$$\begin{aligned}
8 \cdot a + b &\equiv 15, \\
5 \cdot a + b &\equiv 16 \\
\implies
a &\equiv 17, \\
b &\equiv 9.
\end{aligned}
\pmod{26} $$

For #2, congruence gave me:

$$\begin{aligned}
3a &\equiv -1, \\
\text{which is}\quad 3a &\equiv 25, \\
\implies 3^{-1} &\equiv 27,
\end{aligned}
\pmod{26} $$

not $17$. Am I doing something wrong?

After $3a=-1 \pmod{26}$ note that mod $26$ we have $-1 = 25=51=3\cdot 17$, so $a=17$.

Alternatively, note that $3\cdot9=27=1$ so we can multiply both sides by $3^{-1}=9$ and $-9=17\pmod{26}$.

And then $5\cdot17 +b = 9$, and $5\cdot 17=85=7$ and so $b=9$.

Now substitute $p=3$ in the encryption formula $c=17p+9$ for the final question.


Is there a way to project one elliptic-curve element to a subgroup with certain size? For discrete logarithm we can pick a random number $n$ and project it to a subgroup. E.g. given a prime $p$ with
$p-1 = 2\cdot a \cdot b +1$
we can compute
$n^{((p-1)/a)} \equiv n_a \mod p$
after this $n_a$ is an element of a subgroup with size $a$
$(n_a)^a \equiv 1 \mod p$

Is there a way to do something like this for elliptic curves?

Target use case scenario:
1.)random number $r$ is picked
2.)element of elliptic curve $e$ out of $r$ with some function gets computed: $e_r=f(r)$
3.)element which lies in subgroup with size $k$ gets computed: -> $e_{r,k}$  (how?)
4.)repeat 1.-3. for another random number $r$ --> $e'_{r',k}$
target result: A possible attacker who has access to source code and runtime variables should not know how to compute $e'_{r',k}$ out of $e_{r,k}$ with given EC generator $g$.

The subgroup with size $k$ likely (if exists) also has a generator $g_k$. There should be some way to produce $e'_{r',k}$ out of $e_{r,k}$, e.g. with $e'_{r',k} = e_{r,k} \odot g_k^i$. In case multiple subgroups with size $k$ exist which have disjoint elements this only need to be true for elements in same group. The amount of disjoint groups should not be larger than a low number (<1000).

In case that is possible whould it have a significant impact at security?

Is there a way to do something like this for elliptic curves?

Of course; if we have an elliptic curve with order $q = a \cdot b$, then we can make an element $H$ into the subgroup of order $a$ by computing $H_a = (q/a)H$.  And, we have $a H_a = 0$ (the neutral element) precisely as requested.

Now, we typically don't use elliptic curves with an order with two large prime factors; they are usually selected with an order $q = hr$, where $h$ is a small integer (most often 1, 4 or 8) and $r$ is a large prime.  We do this because that makes the ECDLP problem as hard as possible; with your order $q = a \cdot b$, you could compute discrete logs in time $\sqrt{ \max( a, b ) }$, and so we'd have to use a larger elliptic curve that we would otherwise need.


Efficient AES - Use of T-tables I'm really in trouble! I'm trying to understand how the T-tables in AES encryption work. But I don't know if I get the point.
What I understood is that they are used to reduce the whole computation of the iteration of AES just looking at the T-boxes and the XOR operation.
Now, what I got is that:

    State                 M Matrix
┏             ┓       ┏             ┓
┃ d4 e0 b8 1e ┃       ┃ 02 03 01 01 ┃
┃ bf b4 41 27 ┃       ┃ 01 02 03 01 ┃
┃ 5d 52 11 98 ┃       ┃ 01 01 02 03 ┃
┃ 30 ae f1 e5 ┃       ┃ 03 01 01 02 ┃
┗             ┛       ┗             ┛

I have my State matrix and M matrix composed by 4X4 bytes. Each t-table should receive in input one byte and give in output 4 bytes.
Now, in order to create the t-tables i will have in the first table:

T0=(d4*02)+(d4*01)+(d4*01)+(d4*03)
   (e0*02)+(e0*01)+(e0*01)+(e0*03)
   (b8*02)+(b8*01)+(b8*01)+(b8*03)
   (1e*02)+(1e*01)+(1e*01)+(1e*03)

Then the second table should be:

T0=(bf*03)+(bf*02)+(bf*01)+(bf*01)
   (b4*03)+(b4*02)+(b4*01)+(b4*01)
   (41*03)+(41*02)+(41*01)+(41*01)
   (27*03)+(27*02)+(27*01)+(27*01)

And so on...until I'll have 4 tables. Am I right? Now...How can I use these tables?

(You should take a look at page 18 of FIPS 197 where it describes the MixColumns transform).

You're close. Swap the order of your matrices so that you have:

|02 03 01 01| |d4 e0 b8 1e|
|01 02 03 01| |bf b4 41 27|
|01 01 02 03| |5d 52 11 98|
|03 01 01 02| |30 ae f1 e5|

And then you compute the new columns. i.e. the new first column is:

|02 03 01 01| |d4|
|01 02 03 01| |bf|
|01 01 02 03| |5d|
|03 01 01 02| |30|

Which equals:

|02*d4 + 03*bf + 01*5d + 01*30|
|01*d4 + 02*bf + 03*5d + 01*30|
|01*d4 + 01*bf + 02*5d + 03*30|
|03*d4 + 01*bf + 01*5d + 02*30|

And so on.

Do you See the pattern in the sum? Each column in the matrix is multiplied by an element in the column and then they are summed. We can precompute these columns, and compute the above sum using 4 table lookups and 32-bit XOR operations.

The tables will be arrays of 32-bit values which look like this ("|" denotes byte concatenation):

T0[00] = 02*00 | 01*00 | 01*00 | 03*00
T0[01] = 02*01 | 01*01 | 01*01 | 03*00
...
T0[FF] = 02*FF | 01*FF | 01*FF | 03*FF

T1[00] = 03*00 | 02*00 | 01*00 | 01*00
T1[01] = 03*01 | 02*01 | 01*01 | 01*01
...
T1[FF] = 03*FF | 02*FF | 01*FF | 01*FF

T2[00] = 01*00 | 03*00 | 02*00 | 01*00
T2[01] = 01*01 | 03*00 | 02*00 | 01*00
...
T2[FF] = 01*FF | 03*FF | 02*FF | 01*FF

T3[00] = 01*00 | 01*00 | 03*00 | 02*00
T3[01] = 01*01 | 01*01 | 03*01 | 02*01
...
T3[FF] = 01*FF | 01*FF | 03*FF | 02*FF

Using four tables, you can compute the new state matrix with 16 table look-ups and 12 32-bit XOR operations.


How secure is MD5 for one way authentication? I have a server S1 with an Private String (PS) as an identifier shared with a server S2.

Every 10 min S1 publish the hash value of PS+the current time which is used as  public identifier (PI). Every one can see the value of PI in the internet. As S2 has the value of PS, he also use MD5 to get the hash value of PS+the current time and compare it to the value published by S1 and therefore identify that the value provide from S1.

My solution is working but I am wondering how secure it is ?
The private string PS shared between S1 and S1 looks like

PS=KJGFDFGHJK65456789876RFBNJK567Y7654RFGHJhhhHGE457UHKJHCDFG7654RF
hash=md5(hours time in millisecond+PS)
PI=fe**63**7b00-1cf0-11e6-b**d**f4-08002**00**c9a66

I use a mask to get some values from the hash and use them to construct the Public Identifier. The blood values are random values, not taken in consideration to identify the server. If someone collect the keys I am publishing for few days, will it be possible form him to identify the Private String S1 is using to generate public keys, or that the key provide probably from S1 and not another server ? I hope you understand what I mean, my knowledge in cryptography are very basic and it's hard for me to use technical vocabular.

Every 10 min S1 publish the hash value of PS+the current time which is used as public identifier (PI). Every one can see the value of PI in the internet. As S2 has the value of PS, he also use MD5 to get the hash value of PS+the current time and compare it to the value published by S1 and therefore identify that the value provide from S1.

Essentially, you would be using MD5(M + K) as a MAC. That is insecure.

The construction where you append the key to the message and then hash is not a secure MAC when the hash function lacks collision resistance, like MD5 does. (Technically, you need a collision attack on the compression function.)

Even though using a collision resistant hash (like SHA-256) would likely make what you are doing secure, I would recommend using a real MAC. For example, HMAC, for which you ought to find an implementation in almost any programming environment.


Diffie Hellman vs Three Pass Exchange Given an insecure channel, what are the pros and cons of using Diffie Hellman to generate a symmetric shared key and then send encrypted data with this key, or simply use Shamir's three-pass protocol with symmetric ciphers for Alice and Bob to each supply parts of the key to one another?

Though the general idea of a three pass exchange has merit, when implemented using exponentiation over a finite field it doesn't have much advantages over the far more common Diffi Hellman.

Both get their security from the hardness of descrete logarithm. (Though we don't know to reduce Dlog to either).

Obviously a three pass protocol requires more message passing and requires them sequentially. Also in it's simple form only one party affects the final key which could be seen as a disadvantage over a symmetric protocol.

So DH is symmetrical, has fewer messages which don't rely on each other and is more widely adapted and better studied.

If you are not looking at is a key exchange but as a means to send a message the three pass can be apppied to the message directly or the message could be encrypted and sent along with the first message. While with DH you can only send content after the exchange is complete. So the number of messages required for the initiator to send content ia the same 3 messages.

With DH a third party can hold half keys which can be given someone to establish a secure connection. This allows for asynchronous protocols to work well with DH. Won't work with a three pass protocol.


Pairing in Cryptography I am having problems in doing pairing in cryptography. I have tried the PBC library but seems like it doesn't work and I do not understand the documentation because it uses C++ language.

Is there a library for pairing in cryptography using PHP language?

or is there anyone who can explain how pairing works in cryptography with an input and output?
For example: Weil Pairing or Tate Pairing which uses Miller Algorithm.

Thank You

As @fgrieu said [here], cryptography is usually not implemented in PHP. The best you can hope for is a binding/wrapper:

Search "php crypto binding" on Google

Unfortunately because pairings are not widely used in practice it is unlikely that you find them in major bindings, and although there are many bindings/wrappers listed on PBC website I don't see any for PHP.

Again agreeing with @fgrieu, this can be the opportunity to learn C++. Libraries like PBC (but also the RELIC toolkit) provide a rather "high-level" abstraction of pairings so you can use pairings with a few simple lines of C++.

Did you follow the PBC manual? It really takes you by the hand, if you need a basic use of pairings this should really suffice.

The RELIC toolkit does not have such a "beginner-friendly" tutorial but it is maintained (unlike PBC) and I find it nicer overall. To learn how to use RELIC you will have to read the test suite:

https://github.com/relic-toolkit/relic/blob/master/test/test_pp.c

If you decide to learn the use of PBC or RELIC (or MIRACL) and have questions about their use I think (community, correct me?) you might want to post question stackoverflow instead.


What algorithm to use to rotate values in a predefined manner and be able to decrypt them back to the original? What is the best practice to accomplish this? For example, let's have an initial value abc123456 and a seed secret_hash. I want to change the initial value once about every hour to a new value and be able to decrypt any future value back to the original one.

Should I use an external known value, for instance time, in order to encrypt and decrypt, or there is an algorithm that will generate a decrypt-able infinite stream of values just from the seed and the initial value?

As SEJPM suggests in the comments, you could simply derive each successive value by encrypting the previous value using a block cipher (in "ECB mode", i.e. using the raw block cipher directly), with your "seed" as the key:

$$\begin{aligned}
v_0 &= \text{"abc123456"} \\
v_{i+1} &= E_K(v_i)
\end{aligned}$$

where $E_K(x)$ denotes the encryption of the block $x$ using a block cipher with the key $K$.

It's possible that the iteration above might get caught in a small loop, although if the block size of the cipher is reasonably large (and 128 or even 64 bits should be more than plenty), the probability of this happening within any reasonable number of iterations is negligible; the expected cycle length for an $n$-bit block cipher is $2^{n-1}+1$.

That said, if you want to guarantee that your values will cycle through all possible cipher block values before they repeat, you can use the following scheme instead:

$$\begin{aligned}
v_0 &= \text{"abc123456"} \\
v_{i+1} &= E_K(D_K(v_i)+1)
\end{aligned}$$

where $D_K$ denotes block cipher decryption with key $K$, and $+$ denotes $n$-bit modular addition, when $n$ is the block size of the cipher in bits.

Note that, since $D_K(E_K(x)) = x$, this recurrence can also be equivalently written as:

$$\begin{aligned}
v_0 &= \text{"abc123456"} \\
c_0 &= D_K(v_0) \\
v_i &= E_K(c_0 + i).
\end{aligned}$$

That is, each output value $v_i$ is the encryption of a counter $c_i = c_0 + i$, where the initial counter value $c_0$ is the block cipher decryption of the first output value $v_0$.

Of course, if you don't care about the first output $v_0$ having some certain prescribed value, you can simply set the initial counter value $c_0$ directly to some arbitrary starting value (and, if you never use the same key $K$ twice, you could even just always set $c_0 = 0$):

$$\begin{aligned}
c_0 &= \text{whatever} \\
v_i &= E_K(c_0 + i).
\end{aligned}$$

This is very similar to the counter (CTR) mode of block cipher operation.

If you do want to generate multiple output sequences with the same key $K$, one option is to set, say, $c_0 = k \times 2^{64}$ (for a 128-bit cipher block size, like AES has), where $k$ is a unique 64-bit number identifying the output sequence.  This way, you can have up to $2^{64}$ distinct output streams per key, and can generate up to $2^{64}$ output values for each stream without risking overlap with another stream.

This also lets you, given an arbitrary output block, easily identify both the stream the block belongs to (given by the upper 64 bits of the decrypted counter value) and the position of the block in the stream (given by the lower 64 bits).

(Of course, if you don't need quite that many streams or blocks per stream, you could also use a cipher with a 64-bit block size like Blowfish, and $c_0 = k \times 2^{32}$, to shorten your output values by 50%.)


Attacking a variation of the Vigenere with very long key length I am to decrypt the ciphertext YVBCXGJRYHHRCJIUL into its plaintext message. The information that I am given is that the key used in the cipher is very long (equivalent to the length of an entire book) and that the key is certainly longer than the message being encrypted. The only other information I know is that the message encrypted is 2 days of the week, such as "SATURDAYWEDNESDAY."
There is no way to do any statistical analysis to discover key length. I am completely lost as to how I am to accurately decrypt the ciphertext into the correct message.
EDIT: It is known that the days of the week are "in order" and so based on the length of the ciphertext I can determine that it must be WEDNESDAYTHURSDAY or WEDNESDAYSATURDAY. This will reveal to me the first 9 characters of the key, but if the key is never repeated then I cannot use this to decrypt the second half of the ciphertext.

The important part about the length is how many letters appear on those 17 characters:
YVBCXGJRYHHRCJIUL
WEDNESDAYTHURSDAY
WEDNESDAYSATURDAY

We have the plaintext of 12 of the 17 characters. This should probably let us recover 12 character of the key, and then guess the remaining characters based on context (key is probably made of words, not randomly).


How much entropy is generated by 'random' human keystrokes? I'm wondering about using human input as an entropy generator. We all know humans are terrible at making up random numbers or keys or passwords. But what if we let a user 'randomly' type in some garbage. Just smashing the keyboard, so to speak.

How much randomness does that give, or rather, how much bits of entropy would it generate?

Obviously, way less than 2log(number of keys on keyboard), but I'd say 'a few' bits per keystroke feels about right? After one keypress, the next will be either a key close by (with another finger of the same hand) or one on the opposite side of the keyboard (with the other hand). So I would roughly guesstimate that at somewhere between 2 and 3 bits per stroke.

Any insights?

http://csrc.nist.gov/publications/nistpubs/800-63/SP800-63V1_0_2.pdf

This publication from NIST tries to estimate the entropie of user choosen passwords. I know, it is not exactly what you requested, but i think it could be a good indication for the entropy of "random" keystrokes.

Especially Appendix A2 is relevant. The assume the following:

The first character is taken to be 4 bits of entropy
The next 7 characters are 2 bits per character
For characters 9 - 20 the entropy is taken to be 1.5 bits per character
For characters 21 and above there is 1 bit per character

There is a "bonus" of 6 bits of entropy is both upper case and non-alphabetic characters are used

For more detail read the Appendix A.


RSA - How to change the encrypted numerical result into text? I'm aware of the way that the original plain text is converted into a number by taking the ascii numbers of the byte array of the plain text, but doing things the other way around doesn't seem to work.

The encrypted message is pretty much a series of random digits(let's say it's in hexadecimal), which means that some of it will go above the 7F, or 127, limit of ascii. What happens then?

Edit: Ah, my error was that I somehow forgot that ascii was just 7 bits. Anyway, it was useful seeing how the ciphertext can be represented in different ways.

You don't encode the encrypted result of an RSA encryption to text; it's just a sequence of bytes. It makes no sense as "text". In network traffic such bytes can often just be sent as is, but if you're in a text based protocol (mail , HTTP etc.) one could encode the RSA-bytes from the encryption as base64 encoded data, and this is sometimes done. In either case it's not meant for "human consumption", but used in a program. RSA is not a hand cipher...


Value of S and r in Fiat-Shamir Protocol In the book Cryptography and Network Security by Forouzan,in chapter 14, Fiat-Shamir protocol, its mentioned that two large prime numbers p and q are chosen and kept secret. However n=p*q is made public. Then the claimant chooses s which lies between 1 and n-1(exclusive)........

Now here is the doubt: exclusive means he author wants to say that s belongs to the set (1,n-1) with no other restrictions on it.
However, on internet, I have seen sites mentioning that s belongs to the set [1,n-1] but s must be co-prime with n. Now it is equivalent to say that s belongs to the set (1,n-1) since they have mentioned that s must be co-prime with n, so there is absolutely no way 1 and n-1 will be chosen. However the book doesn't mention anything like s must be co-prime with n.
So I am confused with the rules applied in selecting s

Again r, the random number selected by claimant: the book mentions that it must be between 1 and n-1. So , I am confused whether its set is (1,n-1) or [1,n-1].

It's the same situation as for RSA encryption. If you accidentally pick a bad $s$, i.e. one that's not coprime to $N$ then the protocol fails. How likely is this to happen? If you hit a bad $s$, then you can find the factors of $N$, hence you can break the protocol - put another way, finding a bad $s$, whether deliberately or by accident is no easier than factoring $N$ and breaking the whole thing anyway. And the whole reason that you're doing a protocol in an RSA group in the first place is because you believe that your $N$ is big enough that it's infeasible to factor.

As for whether the boundaries $1$ and $N-1$ are included, this really doesn't matter either - if your $N$ is large enough then the chance of accidentally hitting the boundary when you sample uniformly from $[1,N-1]$ is $2/N$ which is tiny.


"Royal Flags Wave Kings Above" I'm a starter to cryptanalysis and in fact to cryptology. Last night I was decrypting a message from a book that I would quite odd. It doesn't make sense. The decrypted message is "Royal Flags Waves Kings Above".

This is what the book says:
"The plaintext message is a mnemonic to remember the turnover positions on the first five Enigma rotors."

My question is what the message means? What does it have to do with Enigma?

A quick internet search delivered this description of Enigma:

  "This meant that the notches were engaged when Q, E, V, J and Z were uppermost on rotors I, II, III, IV, and V respectively and that therefore the turnover positions were R, F, W, K, A, remembered by the cryptanalysts at Bletchley Park by the mnemonic Royal Flags Wave Kings Above."

So this seems to be the right message yes.


Does it make any difference when salting database passwords with Random vs SecureRandom? I want to salt database passwords and then compute the hash but I wonder if I should use Random or SecureRandom? From an attacker perspective would it be easy to break if Random is used or SecureRandom is used or does it make no difference? if yes why? if not, why not?

I am telepathically inferring you're talking about Java here, in which:

Random is a linear congruential generator with a 48-bit seed and no security properties whatsoever, and
SecureRandom is some cryptographic algorithm whose documentation (archived 2019-03-23) is unclear about its security properties, with broken links and archaic references, but of which one might reasonably expect the following two standard properties:

indistinguishability from uniform random (or prediction resistance, next bit test): to anyone who does not know the seed, the output is indistinguishable from a uniform random string of bits; i.e., prior outputs do not help to predict subsequent outputs
key erasure (or backtracking resistance, or forward secrecy): even if the state is compromised, it does not help to recover past outputs

[edit: I just looked closer (archived 2019-02-22) and discovered that the one algorithm supported by SecureRandom does not, in fact, do key erasure at all—it just uses SHA-1 in ‘CTR mode’.  Nice, Java.]

In general, you should use SecureRandom by default unless you have measured an overwhelming performance concern arising from it.  In general, you might get in cryptographic trouble just from the use of Random.  In general, you will never get in as much cryptographic trouble just from the use of SecureRandom, unless loads of other people are in much deeper trouble already.  If you find yourself spending time wondering which one to use, but you haven't measured a performance impact, you are wasting time wondering and you should just use SecureRandom.

OK, you measured a performance impact?  If not, stop reading and go back to the previous paragraph.

What are the security requirements for salts in password hashes?

The purpose of the salt is to thwart multi-target attacks like rainbow tables that save effort by attacking many instances of the same hash simultaneously—that is, the same unsalted hash.  For example, if an adversary is trying to find one password $p_i$ given $\operatorname{MD5}(p_1), \operatorname{MD5}(p_2), \dots, \operatorname{MD5}(p_n)$, they can use a multi-target attack which costs only $2^{128}/n$ and which can run in time $2^{128}/n^3$ if parallelized $n^2$ ways, even though as a 128-bit hash function you might naively expect the cost of an attack to be about $2^{128}$ in the best case that the $p_i$ were chosen by processes with 128 bits of min-entropy themselves.

Using an independent function for each password, as in $(s_i, \operatorname{MD5}(s_i \mathbin\| p_i))$ where each $s_i$ is a distinct salt, thwarts this attack.*  Of course, it thwarts the attack only if everyone on the planet is using an independent function for every password; in other words, if anyone else uses the same salt, then a multi-target attack can still save costs for an adversary.

According to the documentation (archived 2019-04-01), Random is a linear congruential generator with a 48-bit seed.  This seed is so small that even if it were chosen uniformly at random, collisions would be expected after a few million choices, leading to identical salts produced for every output.  It is unclear how the seeds are chosen; it would not be surprising if it were chosen from the time of day and/or the process id, in which case similar applications run at similar times might choose the same seed.

There are cryptosystems where public values like initialization vectors absolutely must be unpredictable in advance, like AES-CBC.  Is it the end of the world to use Random for password hash salts?  No, but it would suggest that you're a too-cool-for-crypto hipster with reckless disregard for user security and/or your auditors' time, but with ample free time of your own to spend dying on hills on the internet.  You're not that hipster, are you?

N.B.:  You should not use MD5 for anything.  For password hashes, you should use argon2, which has exactly the same considerations for salts, but unlike MD5 can use your available resources—time before user expects a response, available RAM, and additional CPU cores—to raise the attacker's costs.

* Using a secret function like $\operatorname{HMAC-MD5}_k$ for a secret key $k$ instead of $\operatorname{MD5}$ can also help—here we sometimes affectionately call $k$ a pepper—but only if there is a meaningful security boundary between the password hash storage and the password hash verification; that's a story for another day.


Does the SHA hash function always generate a fixed length hash? I'm using the SHA1/2 family of algorithms for a particular project. I was wondering if all the SHA algorithms return a fixed length hash regardless of the length of the data.

Yes. By the definition in FIPS 180-4, there are exactly
160 bits in the output of SHA-1
224 bits in the output of SHA-224
256 bits in the output of SHA-256
384 bits in the output of SHA-384
512 bits in the output of SHA-512
224 bits in the output of SHA-512/224
256 bits in the output of SHA-512/256


Can I use PGP key for RSA /AES encrpyption My client provided PGP public key for data encryption. Can I use any OpenSSL [RSA or AES or any encryption] APIs to encrypt the data with this key?

What are the different types of keys available for asymmetric key encryptions?
Is it possible to convert keys from one format to another?

My client provided PGP public key for data encryption. Can I use any OpenSSL [RSA or AES or any encryption] APIs to encrypt the data with this key?

That depends. If the key is an RSA key or - to use the more modern method - contains an RSA encryption subkey, then you should be able to do this.

OpenPGP certainly allows hybrid encryption that uses AES.

  What are the different types of keys available for asymmetric key encryptions?

You can use either the old ElGamal or you can use RSA with PKCS#1 v1.5 padding. Note that sometimes ElGamal is sometimes (incorrectly) also referred to as DH as it uses the same underlying Discrete Logarithm problem (DLP).

There is also an old proposed internet standard RFC-6637: Elliptic Curve Cryptography (ECC) in OpenPGP that indicates how you can use ECIES to derive session keys rather than to wrap / unwrap them.

  Is it possible to convert keys from one format to another?

No. Calculating the public key requires the private key - the public key must be part of a key pair after all. So it is not possible to derive a public key using a public key that uses a different algorithm.

But PGP does allow the holder of the private key to define subkeys. These subkeys could be using any algorithm. Those subkeys need to be signed by the main private key. The sender can then choose any of the valid subkeys to encrypt. Of course this does require you to retrieve an updated "certificate" (PGP container with the public key) containing the public keys.

Beware that OpenPGP may be vulnerable to padding oracle attacks on several levels. You'd better make sure that you do not automate decryption procedures.


Katz/Lindell Problem 2.2 2.2 Prove that, by redefining the key space, we may assume that $\text{Enc}$ is deterministic without changing $\text{Pr}[\text{Enc}_k(m)=c]$ for any $m, c$.

After banging my head against this problem for a few hours, I honestly don't see a modification of the key space that gives the desired result. For all $k,m,$ and $c$ we have $\text{Enc}_k(m)=c$ with a certain probability $p(k,m,c)\geq 0$. What can we do with that?

Note: Katz/Lindell assume that $|\mathcal M|<\infty$, and $\mathcal C$ is defined as the set of as possible outputs of $\text{Enc}$.

You neglected the most important part, I believe; the encryption map itself may be probabilistic which means we might have $$c \leftarrow \mathrm{Enc}_k(m),$$ instead of $$c =\mathrm{Enc}_k(m),$$ which is deterministic. In the first case a second encryption with the same key and message might result in a different ciphertext. Once you realise this and given that the key space is finite consider for each fixed key message pair $(k,m)$ the distribution of the random variable $$\mathrm{Enc}_k(m) $$ over $\mathcal{C}$ and note that this distribution where each probability is a real number can be approximated arbitrarily closely by a rational distribution with rational probabilities.

Let us say $p_i=a_i/b_i,$ is the rational arbitrarily accurate approximate probability for the ciphertext $c_i$ belonging to the set of texts that appear with nonzero probability for the given $(k,m).$ Rewriting the probabilities as fractions with denominator $\mathrm{LCM}(b_i)$ we can now replace the key $k$ with $$\mathrm{LCM}(b_i) a_i/b_i$$ keys all of which will now map deterministically to the single ciphertext $c_i.$

Proceeding this way for each $(k,m)$ pair we obtain a deterministic scheme.


HKDF - Generating a new, random salt per user? Regarding HKDF, the specification says a salt may be re-used.

However, I have set up my system to generate a new, long and cryptographically random salt that persists with the user.  This salt is not a secret. (See the RFC, section 3.1)

In addition, I am taking our unique user identifier and using it as context info for the third parameter in HKDF.

So our HKDF looks like this:

DK = HKDF(MasterKey, PublicUserSpecificSalt, UUID)

My questions are:

Are there any issues with creating a random, user-specific salt, and using this for the salt input in HKDF?  It seems the spec expects the salt to be re-used, which I am not doing.
If I do use a random, user-specific salt, what is the benefit of the UUID as context info? Should I just remove it, since it would add unnecessary complexity?

By HKDF, I guess you mean HKDF-Expand, which takes as input a pseudorandom key, a label, and the output length. A public label is OK, but it is better unique rather than random due to HKDF-Expand's pseudorandom function security. I think using UUID only as the label is good enough.