RSA Key Differences (OpenSSL CLI vs. OpenSSL/ssl.h C function) So, I am sitting here trying to figure out what is happening and why two keys are different in such a vast manner. I've created two key pairs, one key pair with the OpenSSL CLI commands on an Ubuntu 16.04 machine and the other keypair with a C program using the RSA_generate_key functions resident within the  library. However, even though both keys are made with identical parameters, the differnce is farily large within the public and Private key. The difference in Public Keys are 25 bytes and it seems it's not formatted the same either.

OpenSSL CLI:

 openssl genrsa -des3 -out private.pem 4096
 openssl rsa -in private.pem -outform PEM -pubout -out public.pem

OpenSSL CLI Key:

OpenSSL CLI ASN1Parse:

OpenSSL CLI Key Dump (Base64 -d):

------------------------------------------------------------------------------------------------------

C Program:

C Program Key:

C Program ASN1Parse:

C Program Key Dump (Base64 -d):

Attempting to dig into what the RSA_generate_key function does I found this: but, that does not tell me if it is in an ASN1 (Which it looks to be from the header). Or if there a a different formatting applied that I need to duplicate in order to create a key similar to that created from teh C Program. Essentially, I have to duplicatie the extact functionality of the C key generation with the CLI tools.

They're both in ASN.1 (DER) format, however they have different contents.

The OpenSSL version has an outer formatting that effectively states "this is an RSA public key", following by the actual raw public key key (which is listed as a 'bitstring' in the ASN.1 parse).  If you were to parse the bitstring as ASN.1, you'd see the public key, expressed as a sequence of two integers.

In contrast, the C program just has the ASN.1 raw public keyl that is, it's just a sequence of two integers, the values for $n$ and $d$.

The additional outer formatting included in the OpenSSL version accounts for the additional 25 bytes.


Commitment scheme: hiding property Given two commitment schemes $Com_1, Com_2$ (both have the hiding property), I'd like to prove $Com_1(m) || Com_2(m)$ is also hiding.

I built these hybrids and want to show $H_0 =_c H_1 =_c H_2$.

\begin{align}
H_0 &= Com_1(m) || Com_2(m) \\
H_1 &= R_1 || Com_2(m) \\
H_2 &= R_1 || R_2
\end{align}

For $H_1 =_c H_2$: If some $D$ tells apart $H_1$ from $H_2$ then we can distinguish $Com_2(m)$ and $R_2$ by prepending some random $R_1$ and then call $D$.

But how could we prove $H_0 =_c H_1$?

I hope this is not homework. It should be almost the same as proving $H_1=_cH_2$. Just let the distinguisher (that distinguishes $Com_1(m)$ and $R_1$) generate and append $Com_2(m)$ in both worlds. This can perfectly simulate the view of the distinguisher that distinguishes $H_0$ and $H_1$.


How can Shamir's method for secret sharing work in the GF(256)? I have been reading about Shamir's secret sharing, and maybe i completely misunderstand something, but the field is meant to be a prime. However, when i look at the implementations of this algorithm, they all use GF(256).

I do understand the beauty of such field, since that's the best compromise between the size of the chunk of the data and the number of keys that one can generate, but i was unable to find how they got around the requirement of a prime.

Alternatively, of course, i have misread something.

Shamir's secret sharing works in any finite field. A field is a mathematical structure that follows the usual laws of addition and multiplication. A finite field is a field with a finite number of elements, unlike for example the real numbers, which have an infinite number of elements.

Fields exist for all prime powers pk where p is a prime and k a positive integer.

Prime order fields (k=1) are nice because you can use standard modular arithmetic. You add/multiply as usual, and apply the modulo operation in the end.

For other fields operations are slightly harder to understand. If you use simple modular reduction they won't work (e.g. you can't just compute the operations mod 256). Mathematically you use a reduction polynomial. In practice an implementation will use lookup tables.

The most common choices are binary fields with p=2 (including 256 = 28) and prime fields with k=1.


Randomize (encrypted) data to hide the behaviour of the data source I'd like to transmit a small amount of data, typ. 4 - 16 Byte through a channel that can be eavesdropped at any time.

The behaviour, the way the data changes, should be protected too.

I could encrypt it using XOR with a 4 - 16 Bytes key like this:

c = m x k

This means c is the same for the same m. When observing the cipher, it's actually not interesting to decrypt the actual data because the cipher reveals enough information about the data source.

When observing the data - encrypted or not - it should ...

... NOT LOOK LIKE THIS:
t=0 12587200
t=1 12587200
t=2 12587200
t=3 97387419

... BUT LIKE THIS:
t=0 23443623
t=1 53453566
t=2 91372718
t=3 18347444

The data either

lineary increases (with variable increment) or
over a long time period, changes around a relatively fixed average value or
does not not change at all over a long period of time or
is guessable with not much effort

It's clear to me that, since the data might not or little change, it should be randomized before encryption.

Constraints

No security by obscurity - the algorithm is known to an eavesdropper
The data may be

broadcasted by the source (updated in a defined interval, during this time period an eavesdropper may see the same data) or
get actively read by one peer

The receiver/reader may miss a message update so it should be able to sync
Message loss is acceptable for the receiver
Both peers cannot rely on a stable and tamper-free timebase
CPU power and memory requirement is limited
The data and the behaviour can be seen unconfidential after a while

I see one option, suitable for broadcasting and active read: combine the data with a pseudo random factor derived from a confidential IV known to both sides. That combination is then encrypted using the also confidential key.

It could look like this:

 T = 5 mins     # Update interval, e.g. 5 mins (unconfidential)
 K = 0x1BC07410 # Key (confidential)
IV = 0xB9EF72E5 # LFSR seed (confidential)
 r = 1000       # initial rounds (unconfidential)
 R = 0          # LFSR round counter
 n = IV         # pseudo noise from LFSR

def HIDE(m):
  n = LFSR(n)
  return m x n

def ENC(m):
  return m x K

# initialize once
while R < r:
  n = LFSR(n)
  R = R + 1

while True:
  R = R + 1
  m = READ_FOUR_BYTE_MESSAGE()
  Feed to broadcasting or store for retrieval: ( ENC(HIDE(m)), R )
  sleep(T)

It's clear to me that an eavesdropper might brute force probe IVs cycled R times through the LFSR and XOR it with the cipher to know that the message did not change between the update intervals.

My questions

Have I missed other attacking vectors?
Is there anything to improve the security but increasing IV and key lengths?
Please guide me what basics I should learn

I assume that you meant to xor the message with the LSFR state, and not with the fixed key.

Even in that case, one problem that you don't cover is that if the attacker knows/guesses that the data between two different exchanges is the same, he can recover the LSFR state (and from that, he gets everything).

What he would do is xor the two ciphertexts $LFSR^k \oplus P$ and $LFSR^{k+n} \oplus P$; that gives him $LFSR^k \oplus LFSR^{k+n}$; if he knows how large $n$ is (the number of times you cycled the LFSR between the two messages), then recovering the original LFSR state is a simple exercise in linear algebra.

Designing such a system really isn't a task for amateurs; it's far too easy to come up with a system with subtle vulnerabilites such as above.  Instead, I would suggest you use a system designed by an expert.

I was going to write some advice here about how to sketch out such a system; however I realized that I don't know enough about your system constraints and required security model to do it justice.  However, someone needs to do it, and you're not the right person.

I'm not criticizing you; actually, your list of requirements ("the messages need to be randomized", "no security by obscurity", "no reliable timesync", "message loss may happen") shows you've thought about it.  It's just that making an efficient and secure encryption system is a lot harder than it looks.

As for some of the constraints that would need to be considered by an expert:

You mention potential evesdroppers; do you also need to worry about someone modifying the ciphertext (perhaps in hope of making predictable changes in the decrypted data)?
How large can the ciphertexts be?
You said that you had constraints in both time and memory; how tight are those constraints?  Is the memory constaints on program size or data size?  If you're on a CPU, is that an 8-bit CPU, or a 32-bit CPU?
If someone recovers the key somehow, they can read all the data; are you OK with that?


Replay Attack in Stream Cipher Stream ciphers are vulnerable to replay attack if the same key k is used.

If E() is a stream cipher and an attacker intercepts the message m that's being transmitted at time t, how can the attacker compose an encryption of the following for any value of t?

E(k,t || m)

context: An Unilateral Authentication using Time-stamp

The way a stream cipher works, traditionally, is that $E_k$ produces a pseudorandom bitstream (the keystream) based solely on the key $k$. The message is then encrypted by XORing the message with the keystream. This has a number of consequences, notably that if you know both the plaintext and ciphertext, it's trivial to compute the keystream (if $C=M\oplus K$, then $K=M\oplus C$). If you know the keystream, you can then encrypt messages of your choice up to the length of that keystream, even without the actual key.

For this method, it's actually far, far, far worse. The attacker doesn't even need m to do his attack; if you know the plaintext corresponding to some part of a ciphertext, you can then modify the ciphertext so that that part decrypts to whatever you want. For instance, if you know the first 32 bits are a timestamp and know the timestamp $t_1$ (so the message is $t_1||M$), you can then XOR the first 32 bits of the ciphertext with $t_2\oplus t_1$ to get a new ciphertext that decrypts to $t_2||M$.

The lesson is that stream ciphers don't hold up to active attack. That's OK; they're not meant to. To ensure that a ciphertext wasn't tampered with, you need a proper message authentication code like HMAC, which does verify that the person making the message had access to the key. The lesson for other uses of stream ciphers is that you want a message-specific initialization vector so that you don't have the same keystream on all messages encrypted with the same key; then the keystream is $E(k,IV)$, and the IV need not be secret (so you can just slap it on the front of the message). This isn't good to rely on for authentication, though; a MAC is what's made for message authentication.


Does concatenation of two pair computational indistinguishable distributions still indistinguishable? Let $X,X',Y,Y'$ be some distribution ensembles such that $X\sim X'$ and $Y\sim Y'$, where $\sim$ means computational indistinguishable. Define $(X,Y)$ be the distribution ensemble over $\{0,1\}^{2n}$ for each $n$ such that $P[(X,Y)=(x,y)]=P[X=x]*P[Y=y]$ and $(X',Y')$ similarly.

  My question is: Does $(X,Y)\sim (X', Y')$?

I can prove this if all the distributions are polynomial sampleable by a hybrid argument, that is we can show that $(X,Y)\sim (X,Y')$ since if there exist distinguisher $D$ to these ensembles then for a given $y$ we can first sample a $x$ from $X$ and feed $(x,y)$ to $D$, but what if $X$ is not polynomial sampleable?

(I'm new to cryptography, so I'm sorry if this is trivial)

If $(X \approx X')$ and $(Y \approx Y')$, then it holds that $(X \times Y) \approx (X' \times Y')$. Indeed, let us consider an adversary which is able to distinguish $(X \times Y)$ from $(X' \times Y')$ with probability $1/2+\varepsilon$; the adversary returns $0$ if he estimates that the sample comes from $(X' \times Y')$, and $1$ else. Indeed, let us consider an adversary which is able to distinguish $(X \times Y)$. Given access to such an adversary, we construct a distinguisher $D$ for both $(X,X')$ and $(Y,Y')$ as follows:
$D$ asks for a challenge $x$ to the first challenger, which comes from $X$ with probability $1/2$, and from $X'$ with probability $1/2$. Similarly, $D$ asks for a challenge $y$ to the second challenger, which comes from $Y$ with probability $1/2$, and from $Y'$ with probability $1/2$. Then, it sends $(x,y)$ to the adversary, which returns a bit $b$. $D$ simply forward $b$ to both challengers. Note that with probability $1/2$, $x$ and $y$ come from the same side of their pair of distributions (id est, with probability $1/2$ either $(x,y)$ comes from $(X,Y)$ or $(x,y)$ comes from $(X',Y')$). In such a case, the adversary returns the correct guess $b$ with probability $1/2 + \varepsilon$; in the other case, which happens with probability $1/2$ too, the adversary returns the correct guess with probability (at least) $1/2$. Overall, given two challenges $x$ and $y$, and by feeding the pair $(x,y)$ to the adversary, $D$ wins the challenge against both challengers with probability $1/2(1/2 + 1/2+\varepsilon)=1/2+\varepsilon/2$. Hence, up to a factor $2$ in the distinguishing advantage, being able to between $(X,Y)$ and $(X',Y')$ implies being able to distinguish between $X$ and $X'$, as well as between $Y$ and $Y'$.


Are the weaknesses of my s-boxes attackable? I got specific problem with my s-boxes in $128$-bit block cipher. One round of encryption is like that:
input - sbox - reverse block - $sbox^{-1}$ - output
Every s-box got specific $128$-bit key. $sbox^{-1}$ means that we are looking for such input to s-box that will give us such reversed block.
First problem is with numbers divisible by $2$. Every input block in s-box of the form 000...0001... also will give us the same first zeros and one. Fore example:
000001...0111101...
go into:
000001...1111001...
All the rest of the block depends on key and there is no know way to guess it without the key. It also means that block 000...0001 always gives the same block 000...0001 and block of only zeros goes into the same block. It also means that every block with $1$ as the first bit will also go into block with $1$ as the first bit. I think it can be solve, by xoring with some key before every round, let's ignore that problem for now.
Second problem is that every $input + 2^{n}\cdot l$ will give output block with the same first $n$ bits in s-box.
Can you find a way to attack it? Main idea is to avoid problems by reversing blocks and then looking for such input to s-box, that will give us such reversed block - it destroys patterns which we have in that s-boxes. Let's say we want to encrypt block 000...0001. We know what block will gives us first s-box (exactly the same), but without the key of the second s-box we can't tell which number is giving 1000...000 block in that second s-box.

The strengths and weaknesses of an S-Box can be determined by analysis of the commonly agreed within the cryptanalytic community S-Box properties.
The following list of properties have been described in a 2014 paper "Study of S-box properties in block cipher" by Kamsiah Mohamed and colleagues: Robustness, Balancing, Strict Avalance Criterion, Nonlinearity, Differential Uniformity, Linear Approximation, Algebraic Complexity, Fp/OFp, Bit Independence criterion. There may be other important properties as well.
Practical aspects of strong S-Box generation, considering these properties, have been described by Waqar Ahmad Khan and colleagues in a 2011 article "Construction of Cryptographically Strong 8x8 S-boxes".
A toolbox for S-Box analysis have been described by Stjepan Picek and colleagues in a 2016 paper.
Your question was whether we can find a way to attack the encryption scheme based on your S-Boxes, but from the description that you gave, on how you use them, they are not actually S-Boxes, but the keys. In cryptography, the S-box (substitution box) is the basic component of the symmetric key algorithm that performs replacement. In block ciphers, S-Boxes are usually applied to conceal the relationship between the key and the ciphertext to satisfy the Shannon's property of confusion. This property refers to making the relationship between ciphertext and symmetric key as complicated and involved as possible. S-boxes need to be strong, in terms of the properties above mentioned, but they are not necessarily need to be secret. To the contrary, in a Russian GOST 28147-89 (RFC 5830), developed in the 1970s, S-Boxes are secret, and are called "long-term" keys, in addition to "session" keys, so both "long-term" and "session" keys comprise the key. This approach has its drawbacks because the "long-term" key, i.e. the S-Box should be thoroughly analyzed to comply to the properties above mentioned. What you call "S-Box" in your algorithm is actually a key. If what you call "S-Box" is actually a one-time pad, i.e. a truly random key used only once, then it is a completely different matter. The one-time pad was first described by Frank Miller in 1882 and was reinvented in 1917 by Gilbert Vernam who in 1919 was granted an US Patent 1,310,719 for the encrypted XOR operation of one-time pads. So, if what you call "S-Boxes" fit the definition of one-time pads, than you've got the perfect secrecy. But this is unlikely that you meant that. Thus, I would recommend to analyze your S-Boxes according to the properties above described.


Client-side password stretching - danger of the salt being public? In case of using client-side password stretching (plus a single hash on the server) - the server would need to send the salt before authentication, of course.

Though the salt is not considered a real "secret", is having the salt that public a serious consideration for rejecting this method (i.e. client-side password stretching)?

This answer (with more than 600 upvotes) says it's important to keep it secret. I know it's difficult to measure how important something is, but if you could give me some idea, that would be helpful. The reason to do it client side is to mitigate DDOS attacks.

Though the salt is not considered a real "secret", is having the salt
  that public a serious consideration for rejecting this method (i.e.
  client-side password stretching)?

Yes, it is better if the salt is kept secret, but the attacker still has to perform a full-on offline brute-force search even if they know the salt before a breach, it's just that this search can be carried out before a breach and then after a breach only a logarithmic effort per entry is needed for the lookups. And if they don't learn the salt, the "timer" at which brute-forcing starts is pushed back to the point where the database leaks.

Now this exact attack, the ability to pre-compute real-salt-based password hashes before an actual breach is part of the reason why OPAQUE, the current state-of-the-art asymmetric password-authenticated key exchange (aPAKE) exists, as no previous aPAKE defended against this kind of attack.

So TL;DR: Hiding the salt is better, but actually doing so may be considered too much work and it's not the end of the world if the salt leaks.


Schnorr Pubkey Recovery As per How does recovering the public key from an ECDSA signature work?, it's possible to recover public keys from ECDSA signatures.
Is this possible for EC-Schnorr signatures as well?
I'm looking specifically at https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki as a reference on EC-Schnorr, but it seems to have nothing on pubkey recovery.

Fix a group $E(k)$ on an elliptic curve over a field $k$.  Suppose $P \in E(k)$ is a public key.  If a signature on a message $m$ under $P$ is the encoding of a pair $(R, s)$ of a point $R \in E(k)$ and an integer $s$ satisfying (various criteria and) the equation $$[s]G = R + [H(R \mathbin\| m)]P,$$ where $G$ is the standard base point, then you can recover $$P' = [H(R \mathbin\| m)^{-1}]([s]G - R),$$ where $H(R \mathbin\| m)^{-1}$ is the inverse in the scalar ring of $E(k)$, if there is an inverse, which is guaranteed if $E(k)$ has prime order like secp256k1.  In groups of composite order like edwards25519 or FourQ, $P'$ may not be equal to $P$ but it may serve as equivalent to $P$ for the purposes of signature verification.

However, while that equation is discussed as an option in the BIP-Schnorr document, that's not the option they chose.  Rather, they chose a design where a signature is the encoding of a pair $(r, s)$ of a coordinate $r \in k$ and a scalar $s$ satisfying (various criteria and) the equation $$r = x([s]G - [H(r \mathbin\| P \mathbin\| m)]P),$$ somewhat like Ed25519, about which see for a related discussion of key privacy as even further from key recovery.  This leaves you with the snag that to compute $H(r \mathbin\| P \mathbin\| m)$ you must know $P$ already, or know some black magic to break the hash $H$.

So no, the signature scheme in the documented you cited does not enable recovery of the public key from signatures.


Decrypt (homomorphically and symmetrically) encrypted data using (homomorphically) encrypted key? Is it possible to do the following?

Generate symmetric key $K$
Encrypt data $D$ with the symmetric key : $E_k{(D)}$
Encrypt the symmetric key and the encrypted data using homomorphic encryption scheme (e.g. Paillier) with FHE key : $E_{paillier}(E_k{(D))}$ and $E_{paillier}(K)$
Send both $E_{paillier}(E_k{(D))}$ and $E_{paillier}(K)$ to the other third party
The third party (symmetric) decrypt using it and outputs $E_{paillier}(D)$

Yes, this is possible as long as the homomorphic cipher supports all operations necessary to implement the symmetric encryption algorithm. So for a partially homomorphic cipher like Paillier, this will not be possible. With a fully-homomorphic cipher (or somewhat homomorphic cipher configured with sufficient multiplicative depth), this is very feasible, even for standard symmetric algorithms like AES.

For example see Homomorphic Evaluation of the AES Circuit. AES has become a sort of defacto standard benchmark for fully homomorphic ciphers.

See also Ciphers for MPC and FHE, where the researchers look at designing secure symmetric ciphers that are specifically optimized towards homomorphic evaluation.


R-LWE key exchange why using FFT instead of Karatsuba In the paper Post-quantum key exchange for the TLS protocol from the ring learning with errors problem one of the authors, Douglas Stebila, uses the FFT algorithm for polynomial multiplication but he never explains why he did not use a much simpler algorithm such as Karatsuba for polynomial multiplication.

The Ring-LWE (RLWE) parameters choices are (according to Singh, Vikram):

For 128 bits of security, n = 512, q = 25601, and Φ(x) = x^512 + 1
For 256 bits of security, n = 1024, q = 40961, and Φ(x) = x^1024 + 1

So in the worst case: we are multiplying two polynomials of degree 1024 with coefficients at most 40961 with each other. This does not make sense considering that FFT method should be used only for multiplying polynomials with large coefficient:

  In practice the Schönhage–Strassen algorithm starts to outperform
  older methods such as Karatsuba and Toom–Cook multiplication for
  numbers beyond $2^{2^{15}}$ to $2^{2^{17}}$ (10,000 to 40,000 decimal digits).

Question: what was the reason behind it? Am I making a mistake by saying that Karatsuba would outperform FFT considering parameter choices for R-LWE key exchange? Or did the author use this method to make R-LWE key exchange process look overly complicated?

First, as "Hope that's a start" mentioned, your citation is about the algorithms for multiplying integers, not polynomials. For polynomials, the FFT starts to be more efficient than Karatsuba and Toom-Cook methods much earlier, for polynomials of degree between (very roughly) a few hundreds and a few thousands.

However, for polynomials with integer coefficients, it is usually better to take the NTT (number theoretic transform) rather than the FFT, especially if those coefficients are considered modulo a certain $q$. First, you get no precision issues. Second, it is much faster. I have no idea why in the article you mentioned, the authors use FFT and not NTT, so it might be a good idea to ask them.

Now, to answer your question, the efficiency of NTT and Toom-Cook/Karatsuba methods are comparable for parameters equal to those you mentioned. Most lattice-based crypto implementation papers I have seen use the NTT (eg. New Hope), since the underlying rings are usually of the NTT-friendly form $\mathbb Z_q[x]/(x^{2^k}+1)$, and applications such as homomorphic encryption require bigger $n$'s, in which case NTT is clearly faster. That being said, I have seen efficients combinations of Karatsuba, Toom-Cook and schoolbook multiplication (eg. NTRU Prime) in lattice-based crypto.


Encrypting bcrypt hashes I've been asked by a client to give some advice on hashing and as it isn't my area I'm looking for someone who knows what they are talking about.

The client is hashing 4-6 digit PINs (mostly 4 digit) with bcrypt, they have the work factor set as high as the business will allow them but they are worried that due to the small key space it will still be possible to reverse individual PINs. They are now thinking of encrypting the hashes before storing them to add an extra layer of protection. The encryption is fast enough to not affect login times so my suggestion of using the additional processing to increase the work factor instead was rejected.

What do people think? I can't see it hurting and adding the additional hurdle probably won't hurt but I've heard of odd interactions between different algorithms so don't want to say to do it without someone who knows their stuff looking at it.

Your core problem is the fact that you only have about 20 bits of entropy at most (assuming users pick fully random 6-digit PINs which most probably won't). 20 bits of entropy also means that it takes an attacker at most 1,000,000 times the amount of work that you invest for verification to find the password, but the attacker can greatly parallelize the password search and he can use stronger, higher-clocked architectures than you are usingb potentially. So just relying on the password hash is really not an option here.

Right now, I see three solutions to your problem:

HMAC the password or the hash, this has the advantage of being very straightforward and being guaranteed to be non-invertible.
Functionally equivalently one can also append a high-entropy secret to the PIN prior to bcrypt hashing (this is called "peppering" and has the drawback of blocking interoperability with the third approach).
Encrypt the password or the hash, this has the advantage that you could in theory with password hashes that allow it, upgrade the parameters without client-login, however if your encryption key gets leaked so gets the encrypted data
Outsource verification to a rate-limiting HSM, this has the advantage, that an attacker cannot possibly try passwords faster than the rate-limit

Your best option really would be to use a rate-limiting HSM which provides HMAC and then HMAC the bcrypt hashes or directly the passwords.

  They are now thinking of encrypting the hashes before storing them to
  add an extra layer of protection.

Yes, this will bring security up from an attacker just having to exfiltrate and break the hash to an attacker having to exfiltrate and break the hash after he exfiltrated the encryption key (which you can prevent, right!?).

  I can't see it hurting and adding the additional hurdle probably won't
  hurt but I've heard of odd interactions between different algorithms
  so don't want to say to do it without someone who knows their stuff
  looking at it.

While in theory there may be odd interaction, the probability of this happening in practice is negligible.


How to caculate the summation of successive modular inverses? $p$ is a big prime. $p>2^{2048}$.
So how to caculate the summation of successive modular inverses over $p$?
$$
\sum_{i=1}^{\frac{p+1}{2}-1}{i^{-1}}\pmod p
$$
As to $p$ is a big prime, it's impossible to caculate the modular inverses one by one and sum them at last.
I found someone give a formula which approximates the result, but I couldn't prove it.
$$
p - \frac{2^{p}\pmod {p^2}-1}{p} \pmod p
$$
Can you help me prove the formula, or give your answers to calculate the summation? Thanks sincerely!

The sum you are inquiring about is pretty much the right side of the Fermat quotient identity discovered by Eisenstein (proof here):
$$
-2q_p(2) = \sum_{i=1}^{(p-1)/2} 1/i \pmod{p}\,,
$$
where $q_p(a) = \frac{a^{p-1} - 1}{p}$.
Thus the sum can be computed as $-2 \frac{2^{p-1} - 1}{p} \bmod p$. Because computing $2^{p-1}$ is not feasible for very large $p$, and because one only requires the result divided by $p$ and then reduced again by $p$, computing $\frac{2^{p-1} - 1}{p}$ can be performed as $\frac{(2^{p-1} \bmod p^2) - 1}{p}$ without any precision loss. And to absorb that factor of $2$, one can compute instead $-\frac{(2^{p} \bmod p^2) - 1}{p} \bmod p$, which is exactly the formula you found.


Are Stream Ciphers Less Secure? This is by no means a scientific observation, but it seems to me that stream ciphers receive a lot less attention than block ciphers. Is there any reason for this? (Is it because block ciphers are accepted as superior?)

Additionally, since there is no "AES" of stream ciphers, is there any reference of currently secure stream ciphers other than the few green entries on this Wikipedia page? I know about NESSIE/eSTREAM but much of the trust in an algorithm comes not just from its claimed security, but also from the amount of scrutiny it has received, and it seems that none of those ciphers has been the subject of much debate.

The fact that block ciphers can be run in stream like modes diminishes the need for stream ciphers. Add to this the fact that a number of processors today are being built with instructions to speed up AES, and even the performance advantages of stream ciphers is less.

RC4 is still used today, but has shown significant weaknesses and is therefore not recommended in newer designs. The eStream project was put forth to develop new stream ciphers and the ciphers picked for the final portfolio have been well analyzed. They are still probably too new for general acceptability, but I have started to see some of the being used in the wild, especially Salsa20.

Personally, if I were designing a new system and needed a stream cipher, I'd use AES in GCM or CCM. That way you get the streaming capabilities of CTR mode, with authentication.


Is Base64(SHA1(GUID)) still unique like the original GUID? Basically what the title is; GUIDs are unique by design. If you run the GUID through SHA1 and then Base64 the hash, will the resulting string have the same guaranteed uniqueness as the GUID, or not?

Base64 provides a 1:1 transform from input to output (and back again if desired). So if you take a set of unique items and base64 encode all of them they will all be unique.

So the question becomes if you run a GUID through SHA1, will the resulting hash have the same uniqueness as the GUID?

The answer is practically - yes; theoretically not quite. Multiple inputs to SHA1 map to the same output, but in reality if your GUIDs are unique then there is negligible probability that there will ever be a collision leading to loss of uniqueness.


What is the difference between a Stream cipher and a Symmetric Encryption algorithm? According to the Tag definitions:

Stream Cipher: A stream cipher is an encryption algorithm which encrypts arbitrary length plaintext, using a key. Some stream ciphers generate a keystream from only the key, which is then XOR-combined with the plain text, others feed back plaintext or ciphertext into the algorithm to create the keystream.

Symmetric Encryption: Symmetric cryptosystems assume two communicating entities share a pre-established secret key.

What is the difference between these two terms? Is there a particular situation that would be more ideal for a Stream cipher instead of a Symmetric encryption algorithm (or vice versa)? Or are these two simply different terms for the same concepts?

Follow up: ChaCha20-Poly1305 is identified as a stream cipher. Is AES/3DES also a Stream Cipher?

There are multiple ways to do symmetric encryption. The two most popular ones are block ciphers and stream ciphers. So stream ciphers are a subset of symmetric ciphers.

AES and 3DES are block ciphers, not stream ciphers. But if you use them (or any other block cipher) in CTR mode, you can create a stream cipher out of them.

ChaCha20 is a stream cipher, Poly1305 is a MAC (message authentication code) algorithm. Together, ChaCha20-Poly1305 form an authenticated encryption scheme.


Elliptical Curve Cryptography decryption resulting point at infinity? I am building a web app to encrypt and decrypt using an ECC algorithm.

I use the following curve parameters:

Prime p = 43
a = 7
b = 3

public key e1 = 11
private key d = 3
let say i want to encrypt character that is on point (38, 12)

So I calculate its cipher which results in

c1 = (11, 32)
c2 = (27, 40)

I'm sure that both of my cipher is correct because I already calculated it manually.

The problem is, when I want to decrypt it, I have to calculate

M = c2 - d * c1
d * c1 = (27, 3)

so,

M = (27, 40) - (27, 3)

Since point (27, 40) and (27, 3) is a straight line, it will resulting point infinity. Beacuse we can’t calculate the lambda since

x2-x1 = 21 - 27 = 0

and the lambda formula is

y2-y2 / x2-x1

and we can’t divide number to zero.

How to solve this problem? How do I get my original point if my cipher resulting point at infinity?

Summarizing the answer from the comments, starting with poncho:

  Since point $(27, 40)$ and $(27, 3)$ is a straight line, it will resulting
  point infinity.'; actually, not. $(27,40)−(27,3)=(27,40)+(27,40)$, that
  is, we have a point doubling...

which resulted in

  how can $(27, 3)$ can turn to $(27, 40)$ and not $(27, -3)$?

which is resolved by user94293

  $(27,40)$ and $(27,−3)$ represent the same point. Computations are done in
  $\mathbb F_{43}: −3\bmod43=40$


Find some hash function with deliberate collisions I guess this should be well known (or trivially desperate), but I couldn't find any reference.

I have a small number (say $k=15$) of messages $m_i$ ,$i=1\cdots k$ (they are fixed length and short, but I think this should be irrelevant).

I'd like to find some hash function such that $h(m_i)=h(m_j)$ (deliberate universal collision, they all give the same hash), but such that the chance of a random collision is reasonably small. I'm not concerned about cryptographic attacks.

The brute force approach (append some random bytes to all messages, hash, retain some bits and hope that the  universal collision happens) doesn't look practical. Too many tries, too high probability of random collisions.

Is there some other way?

If you just want to prescribe up front that a set of messages $m_1, m_2, \ldots, m_k$ will collide in an otherwise innocuous hash function, without regard for any cryptographic security properties…

…then the question is off-topic for crypto.SE, but you can just pick a hash function $H\colon \{0,1\}^* \to \{0,1\}^\ell$, pick your favorite hash value $h$ for the messages $\{m_i\}$, and define $$H'(m) = \begin{cases} h, & \text{if $m \in \{m_i\}$;} \\ H(m), & \text{otherwise.} \end{cases}$$  In this case, $H'(m_i) = H'(m_j)$, but $H'$ otherwise behaves like whatever kind of hash function $H$ is.  It is unlikely that you can compress the description of $H'$ more than this without additional structure to the fixed messages $m_i$.

Another approach would be to define $\hat H(m) = f(H(m))$ where the polynomial $f \in \operatorname{GF}(2^\ell)[x]$ is the Lagrange interpolation of of the function $H(m_i) \mapsto h$: $$f(x) = \sum_i h\cdot\prod_j \frac{x - H(m_j)}{H(m_i) - H(m_j)}.$$  If the $m_i$ are larger than the $\ell$-bit hash values, this has a substantially shorter description: it is a degree-$k$ polynomial with hash-value-sized coefficients.  (Caveat: If $H(m_i) = H(m_j)$ for any $i \ne j$, this formula doesn't work as written—the denominator $H(m_i) - H(m_j)$ is zero.  In that case, just discard that term.)

Note that unlike $H'(m)$, $\hat H(m)$ does not coincide with $H(m)$ when $m \notin \{m_i\}$.  Whether $\hat H(m)$ has any properties one might expect of the kind of hash function you mean, I leave as an exercise for the reader to ascertain.

(Original answer)  If you were concerned about cryptographic attacks…

You can make a public-key collision-resistant hash function.  Anyone can evaluate the hash function; knowledge of a secret key enables finding collisions; without knowledge of the secret key, finding collisions is conjectured to be difficult.

One example is $x \mapsto y^x \bmod n$ for random $y$, where $n = pq$ is an RSA modulus.  If you know the factors $p$ and $q$ of the modulus, then it is easy to find a collision; if you don't, then it's probably not.  Specifically: any algorithm that can compute a collision with nonnegligible probability can be used as a subroutine to solve the RSA problem, computing roots modulo a large semiprime of secret factorization, without much additional effort.  Under certain additional conditions, finding a collision can't be much easier than factoring for an analogous reason.

VSH is a somewhat more well-known example, defined on arbitrary bit string messages.

These don't allow you to prescribe collisions, however: you get no choice in the messages that collide, only the ability to find them.  Actually you even get the ability to find preimages and second preimages, but again, no control over which sets of messages collide.


Finding public key out of ECDSA certificate I got an ECDSA certificate and now I'm trying to find out the public key. I'm not very familiar with this topic, so I hope you bear my (maybe silly question).

The reason I'm doing this is, because my task is to test the encryption part of a software. Well, actually it doesn't work fine, so the first thing I need to find out is, whether the issue is in the program, or I am the issue.

So I used an ASN1 decoder to read my test-certificate, which told me, that the curve prime256v1 is used and that my public key is

  03 42 00 04 B4 60 C8
  AA 5C 2A 63 20 84 79 D4  E7 73 53 67 A4 9D B9 D0
  9D 56 B1 03 14 D9 65 9B  2D 04 76 CC 0E F9 79 AB
  C3 E5 75 72 25 33 6C 05  FF 40 BA 55 36 45 76 62
  F1 5A 52 6F 57 E8 AB 0E  E0 84 DF 39 3F

If I understood things right, the first octet 03 isn't interesting for me. The second octet 42 tells me, that the key consists out of 66 octets.
Now we come to the interesting part;
The 00 04 tells me, that I'm lucky and no point compression is used, which means, that the abscissa and ordinate Key are easy to find out.

Because of my prime number (related to my prime256v1) I know, that length of X and Y Key is 32 octets. So I take the first 32 octets to form the X-Key and the last 32 to form the Y Key, so

X_Key = B4 60 C8 >AA 5C 2A 63 20 84 79 D4  E7 73 53 67 A4 9D B9 D0 9D 56 B1 03 14 D9 65 9B  2D 04 76 CC 0E

Y_Key = F9 79 AB C3 E5 75 72 25 33 6C 05  FF 40 BA 55 36 45 76 62 F1 5A 52 6F 57 E8 AB 0E  E0 84 DF 39 3F

Because my program requires 36 octets for X- and Y-Key, I add 4 leading zeros to get my result.

I would appreciate, if anyone of you can check the way I painted here and tell me whether I made some mistakes or not.

Thank you very much!

The 00 04 tells me, that I'm lucky and no point compression is used, which means, that the abscissa and ordinate Key are easy to find out.

Nope. The 00 tells you that no bits are unused from the bytes making up the ASN.1 BIT STRING, which is indicated by the first 03 valued byte.'

04 does of course indicate an uncompressed point, so your end result would still be correct.

  Because of my prime number (related to my prime256v1) I know, that length of X and Y Key is 32 octets. So I take the first 32 octets to form the X-Key and the last 32 to form the Y Key

Officially the order of the curve determines the key size. Often there is no difference though. The name of the curve also contains a strong hint about the key size. The public key is however within $0$ and $P - 1$ inclusive (see comment of Poncho below).

  Because my program requires 36 octets for X- and Y-Key, I add 4 leading zeros to get my result.

That should be OK, if the result is indeed interpreted as big endian (network order) value. It beats me why you need to add 4 additional zeros (to the left, I presume), but that might be a hardware implementation issue.


Bellovin 96' attack on IPsec ESP protocol on encryption only option Can you explain the actual attack?

Why does the attacker need to firstly send some arbitrary UDP packet?
How can the attacker break the privacy between A and B?

Link: The article of Bellovin

I'm attaching the slide for a reminder:

Actually, the attack is on CBC mode (which IPSec uses).  In the attack, it modifies the encrypted packets, and uses the IPSec decryptor as a decryption Oracle.

How it works is based on how CBC-mode decryption works:

Note that any particular plaintext block depends only on the corresponding ciphertext block, and the one immediately before it (and the key); as long as those two ciphertext blocks are correct, the corresponding plaintext block will result.

What the attacker does is take the encrypted packet, and replace its payload contents with the message he wants to decrypt (aligned about the cipherblock boundaries).

He then forwards the modified message to the decryptor, which will proceed to decrypt the message.  Now, consider how this decryption will happen for the parts of the message that he has replaced; if we ignore the very first block he replaced, then both the current ciphertext block and the previous one corresponds to the message he is attacking; hence the resulting plaintext will be the plaintext he is attacker.

That is, the resulting decrypted packet will have the plaintext of the message he is attacking embedded in it.

Then, if the security gateway forwards the message, it'll be forwarding a message containing the information the attacker is interested in.

As for your questions:

  Why does the attacker need to firstly send some arbitrary UDP packet?

He needs to send a message that:

Contains an IP header that will eventually get somewhere where he can look at it.  That's why we assume the attacker can't modify a random IP packet; the attacker can't assume he'll see that modified packet.  Instead, he sends a message that's targeted at a confederate; as long as he's careful not to overwrite the inner IP header, that packet will get to somewhere he (actually, his confederate) can see.
Won't be checked to see if any checksums are correct.  UDP can have checksums disabled; that's why Bellovin suggested it.  Actually, it doesn't have to be UDP; any protocol that doesn't checksum its payload would work.

  How can the attacker break the privacy between A and B?

Suppose the attacker sees a message going between A and B that he wants to read.  What he does is generate a packet that'll go through the tunnel between A and B, and is targetted at his confederate.  Once the packet has been encrypted and is traversing between A and B, he grabs the packet, and replaces the payload contents with the message he wants to decrypt (being careful not to disturb the inner IP header and the trailing ESP padding); he lets the modified packet go to B, which decrypts it, and forwards the decrypted packet to the confederate.  The confederate then looks at the internal payload data and see the decryption of the original packet; he wins.


EdDSA (Ed25519) is any random number sufficient for a good private key? Looking at a reference implementation it shows that the key pair generation simply does: read X bytes from RNG and then derive another value from these X bytes thus producing private key with derived public key.

However nowhere in documentation I see mention of what qualifies as a “good” private key (or in this case RNG). Does it mean that any [random] N between 0 and up to 64 byte max value is a “good” private key? Or did I miss any description of how the good quality keys should be generated?

Asking this because this is rather different from for example how RSA keys are generated.

Yes.

In order to understand why, you need to understand how the public key is computed.

The secret key is a scalar. A fixed base point is multiplied by that scalar, and no matter what that scalar value is, you will always end up with a point in the same group as the base point.

You may want to avoid an all-zero secret key but the key space is so large that if the scalar comes from a PRG, this is not something you have to worry about.

The order of the group is 2^252 + 27742317777372353535851937790883648493. The secret should be considered modulo that value. Any secret key between 0 and that value will produce a unique public key.

The secret key can be a uniform value in that range but applications usually just generate a 256 bit key, which doesn't make any practical difference.

Note that most Ed25519 implementations mask the lower 3 bits ("clamping"). So 1 will produce the same public key as 2 or 3. This is a simple way to prevent small-subgroup attacks.
But once again, most applications usually just generate 256 random bits, and don't really have to care about this.


Is encrypting a secret key and being able to decrypt plain text with it possible? Please forgive me if this is a basic question, I'm in high school so I still don't understand very much.

Let's say there are two servers, each with a set of public and private keys. These denote server one: $PK^1, SK^1$ and server two: $PK^2, SK^2$.
Each of the private keys stored on the servers are encrypted with the opposite public key. The private key on server one is encrypted with the public key of server two. The private key on server two is encrypted with the public key of server one.

Data $(D)$ is sent to server one encrypted with $PK^2$. Server one encrypts $D$ with $PK^1$
$D = Enc(PK^1, D)$

$D$ is sent to server two, where $D$ is decrypted so that $D = Dec(SK^2, D)$. This should mean that the data is still encrypted with $PK^1$. Server two sends the data back to server one, where server one gets the plain text by doing $D = Dec(SK^1, D)$.

The benefit of this should be clear, the hosting provider is unable to see either of the private keys, which is a massive benefit to software such as Tor. If a private key of a hidden service is stolen, it is disastrous. This way there is no chance of that happening, unless both of the servers are compromised.

Is encrypting a secret key and being able to decrypt plain text with it possible?

In general, the answer is no.

An asymmetric cryptosystem is one which has the property where a public key and private key can be produced which satisfies:

The public key can encrypt messages, and the private key can decrypt messages.

The private key is computationally hard to recover from the public key.

Any particular message is difficult to recover from just the ciphertext and the public key.

We cannot go from these axioms to the property you have described. (These axioms don't tell you anything about how a given keypair interacts / works with other key pairs)

So now we would have to look at specific cryptosystems. Most cryptosystems have multiple variables in the public key. RSA-CRT has the private key mod each prime. Discrete log systems (typically, there are many exceptions) provide the generator, and the group parameters. So your suggested scheme must be encrypting the private keys element-wise, as you must be able to distinguish between the components.

Lets look at RSA. (not CRT)

Let Server one's original RSA private key (before encryption) be $<d_1>$, and Server two's original private key be $<d_2>$

Your question is then: is the following true $(m^{e_2} \mod n_2)^{d_2^{e_1} \mod n_1} = (m^{e_1} \mod n_1)$

I am stating this without proof (look into modular arithmetic for that), but this will not generally be true due to different modulus being used. To begin with, the former term is defined over n_2, and the latter is defined over n_1.  Then the property that $m^{e_2 * d_2} = m \mod n_2$ depends on the modulus being $n_2$. It is not true over other modulii. (Look into Lagrange's Theorem if your not convinced - https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory))  Your d_2 is taken to a power with an another modulus.

There may exist some cryptosystem where this is possible, but I am not hopeful of it working for any of the common cryptosystems.

To address your suggested use case for Tor, that is not viable. You are gaining no additional protection from a man in the middle, and a server can easily store their private key before encrypting it with another servers public exponent. The alternative would be having pre-encrypted private keys distributed from central authority, but that violates the goal of Tor, and alot of cryptography.


Does knowing common prefixes help crack blowfish? I have strings that are if the form:

 {static data}{changing data}

The beginning static data part is around 20 characters and is common to all strings. The last part is around 5 characters and is different for each string.

The string is encrypted using blowfish (from xjava.security.Cipher) with a fixed initialization vector and a fixed key. Can the fact that the beginning data is unchanging be used as an effective exploit to help break the encryption?

[Edit] Updated to use correct terminology and add a little more information.

The answer depends a great deal about what you're actually doing.

For one, "salt" is not a commonly used term if you are encrypting; public data that is used to modify how the encryption is done is commonly termed an "IV" (Initialization Vector).  However, "salt" is the common term for public data that modifies how a hash is generated.  The distinction between "encrypting" and "hashing" is that hashing can't be undone; given a hash, it's impractical for anyone (even for someone with the key) to generate the original string.

I'll see if I can go through the various possibilities:

If you are actually doing hashing (for example, hashing a password so that you can recognize it if someone enters it), well, what salt does is it protects in two different ways:

If you have two different users which have the same password, differing salts will disguise the fact that the passwords are the same.
It prevents an attacker from getting an attacking multiple passwords at once (for example, by hashing a test password, and seeing if that hash is anyone on the system).

Not doing salt isn't fatal, but generally it is easy enough to warrant the protection it does provide.

And, if you are using PHP's crypt() function (as woliveirajr guesses), well, they always provide a salt -- if you don't provide one, the crypt() function will pick one for you (which is a good thing).  So, in this case, you don't have a problem at all.

In addition, having some fixed text at the start of the string you're hashing doesn't help the attacker at all (if it does, the hash function is seriously broken).
If you are actually doing encryption (that is, you expect someone to be able to decrypt the encrypted string), well, you've got a problem.  Most encryption mechanisms do take an IV, and bad things happen if you keep it constant; exactly what those bad things are depends on which 'encryption mode' you are using:

If you use CBC mode (with a fixed IV), the attacker will be able to see if two encrypted messages are identical up to 8*N bytes in length (for any N).  In your example (assuming the fixed part is exactly 20 bytes long), then this means that the attacker can tell if the first 4 bytes of the variable part of two different strings happen to be the same.
If you use CTR mode (with a fixed IV), it gets a lot worse.  The attacker is able to compute the exclusive-or of any two strings; this will likely allow him to deduce the value of the strings.

In both cases, the correct fix would be to generate distinct IVs, and include those in the encrypted messages.

Also, having some fixed text at the start of the string really doesn't affect the security.  If you pick IVs correctly, it won't affect things at all; if you use a fixed IV, well, fixed text doesn't hurt much.


Is this function a secure MAC? Consider the following function:
$f_k(mm')=\operatorname{HMAC}_{\operatorname{HMAC}_k(m)}(mm')$

Can I use $f$ as a secure MAC?

If you look at $k' = \operatorname{HMAC}_k(m)$ as a key derivation function then you'd expect that $\operatorname{HMAC}_{k'}(mm')$ is secure, even if $m$ is also used to derive $k'$. So from a purely functional point of view then yes, this should be secure.

Also from a functional view I would wonder why there is a repetition of $m$, because as it is used to derive key $k'$ it is already included in the calculation of the MAC value, and repeating it is therefore moot; the repetition of $m$ doesn't do anything for security. You could just use $m$ for the KDF alone, so then the outer HMAC is just $\operatorname{HMAC}_{k'}(m')$

Finally, the presumption is of course that $k$ has enough bits to be used as a HMAC key; generally the same size key as the hash output is recommended.

I don't see any reason why $f_k(mm')=\operatorname{HMAC}_k(\operatorname{enc}(m,m'))$ would not work, where $\operatorname{enc}$ is a canonical encoding function. This is a more efficient MAC if $m$ is large.


Rijndael: explanation of Rcon on Wikipedia? I stumbled onto the explanation of Rijndael Rcon on Wikipedia, and I can't follow it.

The example for Rcon indicates that Rcon(9) is 0x1b.
That could make sense… rcon(9) = (2 ^ (9 - 1) mod (256)) + 16 + 8 + 2 + 1

But I don't understand Rcon(10) or anything past that.

Can someone please explain it to me? Also, why is Rcon(0) = 0x8d?

Rcon(9) is 0x1b because 0x80 multiplied by 0x02 is 0x100, which is reduced to 0x00 xor 0x1b in the finite field.

Rcon(10) is twice Rcon(9), and so forth.

Rcon(0) is 0x8d because 0x8d multiplied by 0x02 is 0x01 in the finite field.

If what I mean by finite field is not understood, it is because the numbers you are dealing with are actually polynomials, see: Rijndael's Finite Field


Is there a hash function whose security can be extended by length? Some old hash functions have been proven to be unsafe. This is mainly due to two reasons:

The computation power of machines are increasing.
People have discovered algorithmic flaws in those hash functions.

Strictly speaking, these two reasons have very different implications. The first may be remedied by extending the length of the block sizes, the number of rounds, or other variables used in the algorithm. But the second reveals intrinsic flaws in the algorithm design.

Hash functions are usually based on simpler cryptographic primitives, and there should be provable reductions from the security of the hash function itself to that of the underlying primitives. Thus I'm wondering whether there exists a hash function whose algorithm design is provably secure (given that the underlying primitives are secure), and its overall security only depends on the length of variables. Such an algorithm can be easily extended to cope with increasing computation power without much effort.

Is there such an extendable algorithm? If so, what is it? And why do people keep inventing new algorithms instead of extending this algorithm? If not, why?

Note: this answer assumes that this is about secure hash applications, not password-hashing which is a different set of algorithms with other properties.

There are a few assumptions in your question that may not be fully applicable:

Some old hash functions have been proven to be unsafe. This is mainly due to two reasons:

The computation power of machines are increasing.
People have discovered algorithmic flaws in those hash functions.

We're still struggling with finding a collision in SHA-1 even though it is considered broken in the theoretical sense. The hash output size of MD5 is not considered large enough for most applications, but it would still be quite a problem to find a pre-image or even a collision using brute force.
SHA-2 and SHA-3 output sizes are out of reach - and will be out of reach - for the foreseeable future, even though the security provided by SHA-224 is below 128 bits (which many believe is about the minimum security you should strive for nowadays).
The amount of computing power required for collision attacks increases exponentially (doubles for each two bits added to the output size). So the amount of computing power does not really threaten the security of secure hashes with large output size.

Hash functions are usually based on simpler cryptographic primitives, and there should be provable reductions from the security of the hash function itself to that of the underlying primitives. Thus I'm wondering whether there exists a hash function whose algorithm design is provably secure (given that the underlying primitives are secure), and its overall security only depends on the length of variables. Such an algorithm can be easily extended to cope with increasing computation power without much effort.
Is there such an extendible algorithm? If so, what is it?

Most of the hash constructions are build up the way you've described. Merkle-Damgärd is used for SHA-2 while SHA-3 uses a sponge construction (using the function $f$ as underlying primitive).
The underlying primitives can usually not be extended to any length / size of the internal state by simply altering a variable. The functions use constants and algorithms for specific word sizes. What is possible is to create multiple versions of the underlying primitives for different sizes of the internal state and output size. This is exactly what has happened for SHA-2 and SHA-3 (Keccak).
It is however unnecessary to go beyond 256 bits of security. Either the underlying primitive / hash construction is broken or the construction stays secure for forever.

And why do people keep inventing new algorithms instead of extending this algorithm?

Because we have doubts on the underlying primitive and the construction itself. Even a secure block that we consider secure (we cannot prove that either) may not be secure for use in a secure hash function. Furthermore there may be specific properties of the construction that become problematic even if the hash is still formally secure. SHA-2 is vulnerable to length extension for instance, while SHA-3 is not.
And don't underestimate the curiosity and drive of individual researchers. There does not need to be any theoretical reason for new hash functions to be published.


Changing an Encryption scheme from AES to ChaCha20 I am using the AES cipher for my OTT platform. Almost all Chip vendors (ARM, Intel, etc) have built-in AES for faster and secure processing.

Now, how feasible it is to move from AES to ChaCha20?  What are the pros and cons of this?
Will ChaCha20 be faster than in-built hardware support for AES?
Can ChaCha20 provide better security over AES over the years?
Do we have any comparison document where it shows performance(cipher speed) over various resolutions starting from 576i to 4K over various bitrate from 2 Mbps to 20 Mbps?

Now, how feasible it is to move from AES to ChaCha20? What are pros and cons of this?

This entirely depends on the platform and implementation. There's no way we can answer this definitively. However it's usually not particularly difficult to change one cipher to another.

Will ChaCha20 be faster than in-built hardware support for AES?

Software ChaCha20 will be slower than hardware AES, but not by much. It will however be much faster than software AES, which is why many people use it. It's also easier to write a side-channel-free implementation in software (hardware AES is resistant to side-channel attacks, but software implementations of AES that are resistant are often much slower).

Can ChaCha20 provide better security over AES over the years?

No way to know. They're both very secure and show no signs of meaningfully weakening.

Do we have any comparison document where it shows performance(cipher speed) over various resolution starting from 576i to 4K over various bitrate from 2mbps to 20 mbps?

A cipher doesn't care about resolution, just data. Any data-based comparison would require knowing exactly what hardware you use and what software you run on it. Let's assume ChaCha20-Poly1305 vs AES-GCM. The answer is simply that the former is faster in a software-only implementation, but AES comes out ahead if the device has anything like AES-NI (even more so if it can also accelerate GCM with something like PCLMULQDQ). But you're probably looking in the wrong place for an optimization. You won't gain much speedup by switching ciphers.

Related: What's the appeal of using ChaCha20 instead of AES?


Is there a way to sign a message without being allowed to see it? I want to sign a message while not being able to see the message.

Logically, there should be a way, I just don't know how this translates into cryptography.

Here is an illustration for what I mean:

A man writes a message on a piece of cardboard. He wraps the cardboard in carbon paper and brings it to another man.

That other man is the signer. He puts his signature on the carbon paper, which in turn also transmits it onto the original piece of cardboard. However, the signer is not able to see the message, since it is hidden in the carbon paper. (The fact that the paper is fragile is without loss of generality, one can image something more tamper-proof of course).

The first man then returns home where he unwraps the piece of cardboard, with the message which is now signed by the signer. But the signer does not know the message still.

There are use cases for this and I would be very interested how this could be reproduced in cryptography.

EDIT: Trying to clarify something, I am sorry my inability to be more clear:

The thing is that the message creator may want to pass the message to third parties that he does not trust. It must be possible for a third party to read the message and verify that the message was signed by the signer. But, assuming that the signer signs many messages every day, it should not be possible for the signer and the third party to cooperate in order to identify which message the signer signed WHEN.

Generally hashing is part of the signature generation. You can use an additional hash or perform the hashing beforehand (splitting the signature generation process), and then only present the hash to the signer. If the message is complex enough then the one-way-hash function hides the message so it cannot be guessed.

You can always include a large enough (128 bit or so) random value with the message so it is impossible to guess the input to the hash value. Of course the receiver has to receive the message and the random value to verify the signature.

A much bigger problem is to make sure that the signer signs the actual message displayed on screen, and not a different hash. So the normal use case of a signature is actually harder to accomplish than your specific task to hide the message.


Is this an example of a zero knowlege proof? My Math Structures professor mentioned the strange concept of a zero knowledge proof to me after class one day, and I decided to do some reading about it. After reading the relatively famous "How to Explain Zero Knowlege Protocols to Your Children", and the Wikipedia page on zero knowledge proofs, I wanted to see if I could construct a protocol for a proof myself. After a bit of thinking, I believe the one that follows completes a zero knowledge proof.

Let Peggy be the prover and Victor be the verifier
Peggy is trying to prove that she knows $(p,q)$

Peggy picks two random large primes $p$ and $q$
Peggy gives Victor $L=pq$
Peggy picks two random large primes $r$ and $s$
Peggy gives Victor $C=rs$
Victor randomly either asks Peggy for either $r$ or $pr$
Victor verifies Peggy's response $m$:

If Victor asked for $r$, he checks that $m\mid C$ and that $C/m$ is prime
If Victor asked for $pr$, he checks that $m\ne C$ and $m\neq L$ and that $m\mid LC$

steps 3 through 6 can be repeated to reduce the chance Peggy could have guessed what Victor was going to ask for.

I think this protocol works because factoring large pseudoprimes is infeasible, and Peggy can fake responses if she knows what Victor is going to ask for.

If Peggy knows Victor will ask for $r$, she just does the protocol as normal (sending $r$ when asked). If she knows Victor will ask for $pr$, she sends $C^\prime=rsn$ initially (for some $n$ and prime $r,s$), and then sends $rn$ when Victor asks for $pr$.

Now I would like if someone more experienced than me could let me know: does my protocol successfully perform a zero knowledge proof? If not, do I appear to have some simply correctable misunderstanding, or did I maybe miss a couple details?

This has some issues, with both soundness and zero-knowledge.

The issue with zero-knowledge is that an eavesdropper who knows $L$ and overhears legitimate traffic can compromise the secret quite easily. While factoring is hard, taking a GCD is very efficient. That means that given $M=pr$ and $L=pq$, an eavesdropper Eve can efficiently compute $\gcd(M,L)=p$. That is a fatal flaw in this scheme as a ZKP -- an eavesdropper can compromise the secret. Where it gets interesting is that your idea of a simulator is correct -- Sam can simulate a valid transaction, which should be enough to guarantee zero-knowledge (Eve could simulate the valid Peggy-Victor transaction without knowing $p$, which would let her efficiently compute $p$ from scratch).

After thinking about this, I think the reason why you can simulate it but it leaks info is that it's unsound (i.e. a prover without the secret can successfully authenticate with 100% probability). When checking $pr$, you verify that $M\ne L$, and $M\ne C$, and $M\mid LC$. It's certainly true that $pr$ meets those conditions. But so does $r$! That's why the fact that a simulator could produce a legitimate-looking transcript doesn't imply zero-knowledge: the transcript only looks legitimate in the protocol because you don't do all the checks you should on it, and further checks on the actual simulated transcript could reveal that it's faked.

The reason simulators are often used to show zero-knowledge is that it means that someone can produce a transcript indistinguishable from a real one without knowing the secret. It's not enough that this transcript passes the tests in the protocol; it must be something that could actually have been produced by a legitimate prover/verifier combo (or computationally indistinguishable from it). If your scheme is unsound, this is certainly not necessarily the case -- an unsound scheme can let a class of transcripts through that are easily distinguishable from legitimate transcripts, which means the simulator might be generating transcripts from the former class.

So, the fatal issue is ultimately that you have $L=pq$ and $M=pr$ both known to an attacker, who can recover $p$. The only reason simulation worked is that you didn't check everything you could have checked; this lets a simulator work, but means that the simulator's transcripts couldn't have been real transcripts (and it's easy to tell that they couldn't have been real), so the simulator doesn't give you zero-knowledge.


Difference between XMSS and MSS-SPR I am currently studying stateful hash based signatures. In the XMSS paper the authors claim that XMSS signatures are 4 times smaller than those of MSS-SPR. However I do not get how it is possible,
because I do not understand the differences between both of them.

As the paper of MSS-SPR does not contain any One Time Signature scheme, a fair comparison should use the same OTS in both schemes. The only other difference I get is pseudo-random versus true random but it is unsufficient because it should not affect signature size:

pseudo-random generation of secret keys must not change the signature at all
pseudo-random generation of salt is helpful to reduce the public key size, but should not change the signature size either

So can someone explain to me where does this factor 4 come from?

As the paper of MSS-SPR does not contain any One Time Signature scheme

Actually, that's not true; they assume Lamport signatures (specifically, a version they call LD-OTS).

When using the LD–OTS, the one-time signature of the message consists of
n bit strings of length n. The veriﬁcation key also consists of n bit
strings of length n, since half of the veriﬁcation key can be computed
from the signature.

Hence, the OTS signature is $2n^2$ bits long; in contrast, a WOTS+ signature (which XMSS uses) is $(n/4+3)n$ bits long, considerably shorter.

Now, the difference is actually larger than a factor of 4 - I believe that, if we take account of the fixed overhead of the authentication path (which is the same in both cases), and MSS-SPR's use of a somewhat smaller $n$, the two are closer.

  a fair comparison should use the same OTS in both schemes.

True; however as specified, the comparison isn't fair.

As for why MSS-SPR uses LD-OTS (rather than some Winternitz-based scheme), I'm not one of the designers, and so I can't be certain.  My best guess is that they couldn't come up with a shorter scheme that preserves the "not relying on collision resistance" property (which WOTS+ does).


How to ensure that a "received value" is not altered? I have a program (whereby people can download and run on their own computers) that will calculate a couple of unknown values each day. For simplicity sake, let's assume that the calculation is simply Rand(0, 1). The program will run and the user will get a value e.g. 0.230957203975.

He will then broadcast this value to anyone interested. He will say "my number today is 0.230957203975!". The problem is that the user can simply lie about the number.

How can we make it such that the user cannot lie? Or rather, how we can detect it if he lies?

I've came up with a solution, but it's sub-par and will be easily defeated. My solution is to broadcast the value 0.230957203975 along with a verification-value calculated as such:

verification_value = SHA2(MD5(RIPEMD(SHA2(HAVAL(GOST(MD5(0.230957203975)))))))

The problem is that the user can examine the machine code, and know the obscure mixture of hash functions used, enabling him to calculate the verification-value himself and lie about the number he had gotten.

I've browsed through Applied Cryptography, but none of the protocols mentioned there seems to have a solution. Is cryptography able to solve this problem?

From my point of view, multi-hashing will slow down things, but it won't add the security you are looking for in this case.

  Is cryptography able to solve this problem?

Yes. What you need is a message authentication code (MAC), which is a short piece of information used to authenticate a message and to provide integrity and authenticity assurances on the message. Integrity assurances detect accidental and intentional message changes, while authenticity assurances affirm the message's origin.

For your further research endeavours, "MAC" and "HMAC" are the relevant keywords.

Nota Bene: In bis comment, @fgrieu hints at practically using a HMAC with SHA256... which indeed seems to be the most logic choice (because it's pretty minimal while currently offering expected security).


Generation of a cyclic group of prime order I am trying to implement a cyclic group generator in Java, but I am running into some issues. In many cryptosystems, the following phrase is expressed during the key generation stage.

  Let G be cyclic group of prime order q and with a generator g

I have done some research on this and have been able to implement a cyclic group generator with a modulus p and a generator g. However, I am currently stuck on how to make sure that the generated group's order is a prime q.

This is what I have:

public class CyclicGroup {
    private static final int EQUAL = 0;
    private static final BigInteger TWO = new BigInteger("2");

    private BigInteger p, g;

    public CyclicGroup(int bitLength) {
        init(bitLength);
    }

    private void init(int bitLength) {
        BigInteger q = BigInteger.ZERO;

        while (true) {
            q = CryptoUtil.getPrime(bitLength);
            p = (q.multiply(TWO)).add(BigInteger.ONE); // p = 2q+1

            if (!p.isProbablePrime(40)) {
                continue;
            }

            while (true) {
                g = CryptoUtil.rand(TWO, p.subtract(BigInteger.ONE));

                BigInteger exp = (p.subtract(BigInteger.ONE)).divide(q);

                if (g.modPow(exp, p).compareTo(BigInteger.ONE) != EQUAL) {
                    break;
                }
            }

            break;
        }
    }

    public BigInteger getRandomElement() {
        return g.modPow(CryptoUtil.rand(BigInteger.ONE, p), p);
    }

    public ArrayList<BigInteger> getElements() {
        // This method is horribly ineffective for large groups and should not be used

        ArrayList<BigInteger> elements = new ArrayList<BigInteger>();

        BigInteger index = BigInteger.ONE;
        BigInteger element = BigInteger.ZERO;

        while (element.compareTo(BigInteger.ONE) != EQUAL) {
            element = g.modPow(index, p);
            elements.add(element);

            index = index.add(BigInteger.ONE); // index++
        }

        return elements;
    }

    public BigInteger getModulus() {
        return p;
    }

    public BigInteger getGenerator() {
        return g;
    }
}

The above class generates a cyclic group with modulus p and a generator g. The following code will produce the subsequent sample output. Note that the tiny bitlength of 4 is to avoid huge numbers in the sample output.

public class App {
    public static void main(String[] args) throws IOException {
        CyclicGroup cg = new CyclicGroup(4);

        System.out.println("Modulus (p): " + cg.getModulus());
        System.out.println("Generator (g): " + cg.getGenerator());
        System.out.println(cg.getElements());
        System.out.println("Random element in group: " + cg.getRandomElement());
    }
}

  Modulus (p): 23

  Generator (g): 9

  [9, 12, 16, 6, 8, 3, 4, 13, 2, 18, 1]

  Random element in group: 9

To sum up, how can I make sure that the generated cyclic group's order is prime? In the above sample output I got lucky that its order is 11. It would also be nice to be able to make the determination without computing all the group's elements and then to count them.

I appriciate any help you are able to give me on this. For your information, my background in group theory is limited at best. Thanks in advance.

One way to do this, if you're working with a multiplicative group $Z^*_p$, is to pick a prime $p$ so that $p-1$ has a large prime factor $q$; once you have this, then to generate a generator of order $q$, you pick a random value $h$, compute $g = h^{(p-1)/q}$, and if that is not 1, then $g$ is a generator of your group.

Obvious questions:

How do you find a large prime factor $q$, given that $p-1$ is hard to factor?  Well, you pick the prime factor $q$ first, and you look for a prime $p$ in the form $kq+1$.
How likely is it that $h^{(p-1)/q} \ne 1$?  Well, if $h$ is selected randomly from the range $[1, p-1]$, that will be one with probability $1/q$, and so you'll almost always get a usable $g$ with just one random $h$.

Another way to do this is pick a prime $p$ with $q = (p-1)/2$ also prime and $p \equiv 7 \pmod{8}$.  In this case, $g=2$ is guaranteed to be a generator of order $q$.  This is a bit more work, however you can use the primes $p$ from this RFC; all those primes have these properties.


Merkle–Damgård transformation example I m looking at this Example of Merkle–Damgård

I have a similar question about this topic.

  I have hash function maps 256b blocks into 128b blocks, how many rounds are
  required for hashing a 140KB file?

My idea is to transform this 140kb into byte (140000 bytes) and divided this number on 256 ... So I have 546,875.
So my hypothesis is that function use about 547 round, 546 are full of byte, and last round have some zeros inside?

I'm thinking good...or I'm too far?

Well, not exactly.

The hash function that your MD internally uses a compression function $f:\{0,1\}^{256} \to \{0,1\}^{128}$

MD construction uses an IV, in your case 128-bit feed into the first call $f$.

The first input and output of $f$ is $h_1 = f(IV\mathbin\|m_1)$. From these, you can deduce that you must divide your message $m$ into 128-bit blocks. 1093 rounds that make 1093*128 = 139904 that is 96-bit less than a full block.

Therefore you need padding and also protection against length extension attacks.

Assume that we simply use the last 64-bit as the big-endian length encoding and padding is 1000000...000Length_in_64_bit. In the end, we require that the size after the padding is a minimum multiple of 128. In your case, your message becomes

$$m =\texttt{M}\mathbin\|\texttt{100...0}\mathbin\|\ell$$ where $\ell$ is the encoding of your length. 96 bits don't leave space for a 1 and encoded length. Therefore you need 1095 round that is 140160 bits.

Now you can divide your message into 128-bit blocks say; $m_1,\ldots,m_{1095}$

\begin{align}
  h_0 &= f(IV\mathbin\|m_1)\\
  h_i &= f(h_{i-1}\mathbin\|m_u), \quad 1<i\leq 1095\\
  H(M) &= h_{1095}
\end{align}

Note that, MD can also apply a finalization with $g$ in the end. In this case $$H(m) = g(h_{1095})$$


Can anybody please explain why is the probabilty of finding a desired message for random chaining values equal $2^{-224}$? Can someone explain why does probability is equal $2^{-224}$ in the following piece of paper?
The length of messages blocks in Hamsi is equal 32 and the length of chaining values is equal 256.

The second paragraph of section 2 of the quoted paper tells the domain of the function $\mathcal F:\{0,1\}^{32}\times\{0,1\}^{256}\to\{0,1\}^{256}$.

Under the reasonable assumption that for fixed second input ($h_{i-1}$ in the question's statement), $\mathcal F$ behaves as a random function of the first input ($M_i$ in the question's statement), then for each value of the first input the probability that the output matches a fixed target value ($h^*_i$ in the question's statement) is $p=2^{-256}$. That will be repeated for the $n=2^{32}$ possible first inputs.

One way to conclude is to know that if an event has probability $p$ of occurring at each (independent) experiment, then the expected number of events for $n$ experiments is $n\,p$, and the probability of at least one event is barely below that value $n\,p$ as long as it remains small. Here $p=2^{-256}$, $n=2^{32}$, $n\,p=2^{32-256}=2^{-224}$ (as asserted in the question's statement). That's very small, thus the approximation made is valid.

The more mathematical way: the probability of no match for one first input is $1-p$. The probability of no match after $n$ inputs is $(1-p)^n$. The probability of at least one match after $n$ inputs (as discussed in the question's statement) is $1-(1-p)^n$. Using that $1-(1-p)^n=1-e^{n\log(1-p)}$, that $\log(1-p)=-p+o(p)$ (using little-O notation), that $e^x=1+x+o(x)$, it comes that $1-(1-p)^n=n\,p+o(n\,p)$. Hence $1-(1-p)^n$ is about $n\,p$. The error made with this approximation is always by excess. When $n\,p<0.3$, the relative error is less than $16\%$. For lower values of $n\,p$, that upper bound of the relative error becomes barely above $n\,p/2$.

Other useful data points are that if $n$ is large, then $n\,p=1\implies1-(1-p)^n\gtrapprox1-e^{-1}\gtrapprox63\%$; and $n\,p=2\implies1-(1-p)^n\gtrapprox1-e^{-2}\gtrapprox86\%$ This explains the "high probability" after about $2^{224}$ random values of $h_{i-1}$ in the question's statement.


What would be the most efficient way to find two large (2048bit) integers $k$ and $q$ such that $p = kq + 1$ is prime and so is $q$? What would be the most efficient way to find two large (2048bit) integers $k$ and $q$ such that $p = kq + 1$ is prime and so is $q$?

Is there some standard algorithm that I could use?

What you ask is basically DSA parameter generation (albeit with a larger $q$). This is described in FIPS 186-4, section A.1.

Conceptually, prime generation is merely: make a random integer, see if it is prime, loop if it is not. In this case, you will want to do things the following way:

Generate a random integer $q$ of the intended size (2048 bits). You'll want to make sure that the top bit it set (because you want a 2048-bit integer, not a 2047-bit or less integer). You also set the bottom bit so that $q$ is odd (if it is even then it is not prime).
Test if $q$ is prime. If not, go back to step 1. The normal primality test is Miller-Rabin. If you use an existing big-integer library, then chances are that it already offers that test.
Compute the proper range for $k$. Basically, if you want the final $p$ to be exactly 4096 bits in length, then set $k_l = \lceil (2^{4095} - 1) / q \rceil$ (division of $2^{4095}-1$ by $q$, rounded up) and $k_h = \lfloor (2^{4096}-1) / q \rfloor$ (division of $2^{4096}-1$ by $q$, rounded low). You need $k$ to be such that $k_l \leq k \lt k_h$.
Set $s = k_h - k_l$.
Generate a random $r$ integer between $0$ (inclusive) and $s$ exclusive. A good way is to generate a random sequence of bits of the size of $s$ (i.e. if $s$ has length 2049 bits, generate 2049 bits); of the generate value does not fit in the range, then try again. This should ensure uniform selection in the range.
Compute $k = r + k_l$, then $p = kq + 1$. Thanks to how $r$ was generated, it is quaranteed that $p$ has the proper size.
Test whether $p$ is prime. If not, loop to step 5.

The only semi-smart thing here is that once $q$ is generated, you don't have to do it again. So it is just two successive but not nested loops, one for $q$, then another one for $k$.

In practice, finding a random prime has complexity between $O(n^3)$ and $O(n^4)$ (where $n$ is the length of the prime, in bits)(exact value depends on how well the primality test is written, in particular when it comes to avoiding the Miller-Rabin test for composites with small prime factors) so the loop on $p$ will be eight to sixteen times more expensive, on average, than the loop on $q$.


Is there another resource for Carter-Wegman-style message authentication? I'm wondering if there are other resources that cover Carter-Wegman style message authentication, besides the sources themselves.

Is there an online text or a book that covers their ideas?  I'd prefer something that's very thorough, and less importantly, free.  I'm just really trying to get a feel for their ideas and related works.

Wikipedia covers VMAC, which is an application of their ideas, here:
http://en.wikipedia.org/wiki/VMAC

LINKS

The original sources are linked through http://www.dblp.org/search/index.php#query=author:mark_n_wegman:&qp=H1.1000:W1.4:F1.4:F2.4:F3.4:F4.4

...and you can refine the search to just Wegman and Carter's works by clicking on Carter on the right side.

You didn't mention at what level you're hoping for, so I'll provide a few resources, and you can figure out which ones best meet your needs.

UMAC: Fast and secure message authentication. John Black, Shai Halevi, Hugo Krawczyk, Ted Krovetz and Phillip Rogaway, CRYPTO 1999.  (This research paper describes UMAC, a fast Carter-Wegman style hash.  It also gives a lot of good background on the topic.)
Wikipedia's entry on UMAC gives some background on universal hashing and its relevance to message authentication.
On fast and provably secure message authentication based on universal hashing, Victor Shoup, CRYPTO 1996.  (This research paper gives some of the theory behind universal hashing.  It might be a tough slog if you are not a theoretician.)
Stronger security bounds for Wegman-Carter-Shoup authenticators. Dan Bernstein, EUROCRYPT 2005. (Even more of the theory behind universal hashing.  An even tougher slog, if you are not used to theoretical crypto, but good stuff if you are.)
If you want to learn some of the crypto-theory, here are some resources:

You could start with Chapter 7 of Bellare and Rogaway's lecture notes on modern cryptography, which provides an introduction to message authentication from a theoretical perspective.  Read to the end of Section 7.4, then you can skip 7.5, 7.6, and 7.7, and jump straight to 7.8, which describes universal hashing -- but is unfortunately as yet incomplete.
You could read Katz and Lindell's Introduction to Modern Cryptography.  Start with Chapter 1, then Chapter 4 (particularly 4.1-4.4).  Unfortunately, while they have a good treatment of the theoretical foundations of message authentication, they don't cover universal hashing as a method of message authentication.

These days, Carter-Wegman-style message authentication is often mentioned under the name "universal hashing".  That search term may help you find a lot more.


Shamir Interpolation Problem (Recovering secret with fewer parts than the threshold) I'm studying about polynomials and interpolation with shamir secret sharing. I have some questions about it.

I found that there are always lower-degrees polynomials that intersects with 2 or more points (passing through 0) with another polynomial of degree at least 3 (in Zp).

Example: Supose a secret sharing scheme with threshold $5$, with the polynomial $x^4$ in $Z_{11}$ and the secret is $0$. Theoretically i could only recover the original polynomial and consequently the independent term (secret = $0$) if i have at least 5 points, right? However, if i combine correctly some shares $(x, f(x))$, i could recover another polynomial with the same independent term, and consequently, the secret. For example, instead of combining 5 points, i could combine the points $(1, 2, 8)$ with their evaluations and recover the polynomial $g(x) = 7x^2 + 5x + 0$. This gives to me the secret $0$.

Now supose all the polynomials $a_4x^4 + a_3x^3 + a_2x^2 + a_1x + a0$ where $\{a_4, a_3, a_2, a_1, a_0\} \in Z_{11}$.

All polynomials of degree 3, 4, ..., $n$ have this property. Some secrets could be recovered with 2, 3, ... points and others only with 2 or 3 or more points. Note that even using less points (2 or 3) its not monotonic.

Questions:

1 - Is it correct to say that there is some kind of "failure" of shamir secret sharing scheme because of this combination of points?

2 - Could i prove that there are always less degree polynomials that intersects with high degree polynomials in point 0 and another one in $Z_p$?

Edit: I've made some experiments.

I have picked all combinations $C^p_2$ and $C^p_3$ of $(x, (fx))$ to all polynomials $ a_3x^3 + a_2x^2 + a_1x + a0$ where  $\{a_3, a_2, a_1, a_0\} \in Z_{5}, Z_{7}$ and $a_3 > 0$. I can always recover the secret using less points than the threshold.

Thanks to everyone!

I have picked all combinations $C^p_2$ and $C^p_3$ of $(x, (fx))$ to all polynomials $ a_3x^3 + a_2x^2 + a_1x + a0$ where  $\{a_3, a_2, a_1, a_0\} \in Z_{5}, Z_{7}$ and $a_3 > 0$. I can always recover the secret using less points than the threshold.

From your comments, it sounds like when you say "I can always recover the secret" what you mean is that there is some subset of shares that results in the correct secret. Not that all subsets of shares always reveals the correct secret.

That is the expected behavior. Under the typical usage of Shamir secret sharing, a subset of fewer than the threshold can use their shares to try to recover a secret, but they will have no idea if they are correct, and their probability of being correct is no better than random guessing.

You said in a comment that "if you consider that the Dealer can be malicious". Shamir never claimed (or proved) the scheme to be secure in the presence of a malicious dealer. For that threat model, you would have to use other schemes.


Initialization vector based on data which can be changed by an attacker We need to exchange some data encrypted between a device and our software where the device does not have access to a source of randomness. Both the software and the device know the key (although they cannot access it, they can only use it for encryption using AES). We are planning to use AES in CCM or CBC (depending on authentication requirements and capabilities of our crypto library) mode for encryption.

Is it wrong to send a randomly generated value from the software to the device, hash it using SHA-256, and use that for the initialization vector?

Or is it better to send the randomly generated value encrypted as well (we can generate a proper IV on the software side)? I guess it would then matter more whether we use CCM or CBC.

The communication between the device and the software can be intercepted and changed by the attacker.

The communication between the device and the software can be
  intercepted and changed by the attacker.

Because of this, you really should use authenticated encryption (e.g. CCM).

  Is it wrong to send a randomly generated value from the software to
  the device, hash it using SHA-256, and use that for the initialization
  vector?

For CBC, the IV needs to be unpredictable to an attacker. Hashing an attacker-known values doesn't make this value unpredictable, however if you encrypt the the value sent to your device using your AES engine, this value would be unpredictable and thus suitable as an IV for CBC.
Note though: CCM doesn't require an unpredictable IV and thus a simple (monotonic) counter would do, as long as the IV / nonce isn't re-used for the same key on either side.


Understanding how SHA-512 achieves its design goals The Wikipedia entry on SHA-2 contains a usable pseudocode recipe. In the hope of some deeper understanding, I implemented SHA-256 and SHA-512 from it. This was helpful, but I still don't think I have joined together my understanding of how the hashing works, and how it achieves its goals.

In short, I can see some non-linear bit-twiddling and likely chaotic behaviour from the components that SHA-2 strings together, but I'm missing how the whole algorithm results in provably achieving the avalanche effect or anything similar.

In discussions here, posters tend to treat the hash output as essentially a random map from any set of input messages whether they have any correlations or not (e.g. they could be random messages to hash, or they could be from a simple series such as integers from 1 to 1000). I'd like to know whether and how this property of SHA-2 is proven or verified.

Here is my understanding so far:

The initial hash data and round constants, derived from square roots and cube roots of prime numbers, are not relevant. The numbers are chosen this way to demonstrate lack of bias (or hidden backdoors) by the designer. You could equally use the binary expansion of $\pi$ sequentially in each constant.
The main design purpose I see for the hash and round constants is that they will push the non-linear repeated rotations into a more chaotic mode when they are added in; and in combination they basically ensure there is no single input word value that has simple short loops when repeatedly calculating e.g. Sum $s0 = (a \ggg 28) \oplus (a \ggg 34) \oplus (a \ggg 39).$ in each round.
The sums in the round and used to initialise the workspace seem have the effect of "spreading" message bit values throughout each word (either in the workspace, or one of the hash sub-components), and as far as I can see the specific values of amount of rotation (28, 34, 39 in the example) are not highly important, other than each value is different between sums/sigmas and they do not form short loops modulo either each other or with the word size.
I can see that some important pieces of feedback in addition in the rounds (e.g. to create temp1 the value of h is used - if it were not used somehow for either temp1 or temp2, its value would become irrelevant). But in general I have no clue why the results from the sums are combined in the specific way given. For instance, why is e negated as part of creating ch?

I do not expect to go from this level of understanding to full comprehension in one step. I'm also not 100% sure about any of the above. In general, I can see how SHA-2 works its magic in a hand-waving way - I might say "it is a complex system built using a few base algorithms with chaotic behaviour interacting". But I am stuck getting to the next level.

How do I find out why the specific recipes for e.g. ch and maj are used (the names chosen in the Wikipedia article imply they have meaning in the design)?

What form does the proof that SHA-2 does what it intends to do take?

SHA-2, like SHA-1, is an ARX hash function: that is, it uses Addition, Rotation, and eXclusive-or for bit diffusion.  The purpose of each one is explained very simply and clearly by Khovratovich & Nikolić in their paper Rotational Cryptanalysis of ARX, so I will simply quote them here:

  Addition provides diffusion and nonlinearity, while XOR does not.  Although the diffusion is relatively slow, it is compensated by a low price of addition in both software and hardware, so primitives with a relatively high number of additions (tens per byte) are still fast.  The intraword rotation removes disbalance between left and right bits (introduced by addition) and speeds up the diffusion.

So there is no "chaotic behavior interacting", but there is bit-diffusion, and that is what you want in a hash.  Sufficient bit-diffusion is called an "avalanche effect".  The message expansion mixes the bits between words, and the actual compression function is where the nonlinearity comes in, using these pre-mixed bits.

As to the second part of your question, $\operatorname{ch}(a,b,c)$ is the "choice" function: when $a$ is $\text{true}$, the result is equivalent to $b$, and when $a$ is $\text{false}$, the result is equivalent to $c$.  So $a$ acts as a selector between either $b$ or $c$.  $\operatorname{maj}(a,b,c)$ is the "majority" function, which takes the majority value as the final result.  So if two or three of the variables are $1$, then the result is $1$; otherwise, the result is $0$.  And usually there is also the $\operatorname{par}$ function, which is "parity" and uses XOR between the operands.

The truth density of each of these functions is 50%.  In other words, given completely random values for $a$, $b$, and $c$, you have a 50% chance of getting a $1$ or $0$ result.


Implementations of Ntru TLS Has anyone come across any implementations of Ntru TLS? I'm working a project for uni that does quantum secure encryption. It relies on a mix of Ntru & AES, but I can't find an implementation of Ntru TLS anywhere. (CyaSSL claims to have one but it needs a license to compile, I've contacted them, waiting to hear back)

Specifically, the following ciphers:

TLS_NTRU_NSS_WITH_RC4_128_SHA
TLS_NTRU_NSS_WITH_3DES_EDE_CBC_SHA
TLS_NTRU_NSS_WITH_AES_128_CBC_SHA
TLS_NTRU_NSS_WITH_AES_256_CBC_SHA
TLS_NTRU_RSA_WITH_RC4_128_SHA
TLS_NTRU_RSA_WITH_3DES_EDE_CBC_SHA
TLS_NTRU_RSA_WITH_AES_128_CBC_SHA
TLS_NTRU_RSA_WITH_AES_256_CBC_SHA

Or – even better – has anyone encountered any type of SSL/TLS implementation that doesn't rely of the discrete logarithm problem, factoring prime numbers, or elliptic curves? I've scoured the internet and come up with nothing.

The open source version of CyaSSL contains code that calls into the commercial NTRU library -- the library itself is missing of course. You might be able to make CyaSSL work with the open source NTRU implementation at https://github.com/tbuktu/libntru ; it's alpha level software though.


SHA-256 "almost unique"? I have seen numerous references on the internet of people describing SHA-256 as generating an "almost unique" hash.

Exhibit A. there are more.

Is there some mathematical basis to the almost uniqueness? I would have thought that as SHA-256 is an evenly-distibuted (?) hash algorithm which can accept any message (infinitely many) as an input and produces a fixed length (finite) hash - then there will in fact be an infinite number of each possible output - which I would think hardly qualifies as "almost unique".

Is there a basis for this statement?

Theoretically, since the domain of SHA-256 contains $2^{2^{64}-1}$ different messages and the value set only contains $2^{256}$ different message digests, there must exist at least one possible output that has more than one possible pre-image.

Another important point is that SHA-256 is a deterministic function. This means that if you hash the same message twice, you will get the same digest both times. Hence, "almost unique" should be understood as meaning that SHA-256 will likely produce a different hash for each different input message. This might be false in an abstract mathematical sense, but it is probably true in a more practical sense:

In practice, uniqueness is not determined by the abstract theoretical non-existence of collisions, but by the practical non-existence of collisions. In order to find a collision in SHA-256, you would probably have to execute the algorithm some $2^{128}$ times. It is unlikely that this will happen anytime soon, even if you count the total number of times SHA-256 will ever be executed by anyone in the entire universe combined.

Does a message "exist" if it belongs to a well defined abstract set, or does it "exist" because it has actually been produced and has been represented by someone or something in the physical reality?