$L^3$ Grover search of NTRU variants I was reading a text on cryptology  by Wayne Patterson and came across the $L^3$ algorithm which reduces integer lattices with respect to their base.  I've also read on the NIST CFP A8 that attacks based on Grover's algorithm aren't really seen as viable.  There is already research covering vulnerabilities in the group rings of NTRU variants, and additional research showing approximate closest vectors return approximate shortest vectors in polynomial time.

Page 70 from "Mathematical Cryptology for Computer Scientists and Mathematicians" by Wayne Patterson states: "The central algorithm developed (and proved to run in polynomial time) by Lenstra, Lenstra, and Lovasz is the reduced basis algorithm. The algorithm begins with any basis $\beta_{i}$ for an integer lattice, and eventually computes a reduced basis in the sense of the previous section." Page 72 then demonstrates how to apply the LLL algorithm in a Shamir attack against knapsacks.

Quoting again from Patterson, "These two theorems (6.1 and 6.2) taken together give an estimate on how close a vector of the reduced basis must be to the shortest (non-zero) vector in the entire lattice." pg. 70.

  My question: Why would it be infeasible to encode the LLL reduction
  and group structures of NTRU variants as a search space in a Grover
  search to return an output that would break the NTRU schemes?  This would be in line with the Coppersmith and Shamir lattice attack from section 4.2 in the linked article of NTRU Variants.

This seems in line with oracle access to a subroutine based on the linked research by Goldreich, et al.

  Phrased differently, Can we know with certainty that LLL reductions
  and lattice attacks will not be made stronger if supplemented with
  Grover searches?

Currently there is (at least) one paper in the lattice literature regarding speeding up lattice basis reduction with Grover search: A Faster Lattice Reduction Method Using Quantum Search. Indirectly, there have also been a few theoretical improvements to subroutines of lattice basis reduction, such as speeding up solving exact SVP with quantum search.

In practice though, the current fastest method in high dimensions is probably BKZ, using lattice enumeration with extreme pruning as the exact SVP subroutine. For this combination of methods, I do not believe anyone ever came up with a significant speedup based on Grover searching, as both methods do not involve a straightforward search over a long, predefined list.

Remark 1: Grover searching generally leads to a decrease in the time complexity for solving a hard problem from $T$ (classically) to at least $\sqrt{T}$ (quantumly). With $T$ scaling exponentially in the lattice dimension, this means we need to increase the lattice dimension by at most a factor $2$ to maintain security. Commonly such improvements in the runtime are not considered a "break" of the scheme.

Remark 2: All of the security estimates for cryptography are just that: estimates. There is no proof that no (classical or quantum) algorithm can quickly solve problems which we now presume are hard to solve. We just don't know any fast ways to solve these problems. So we do not know with certainty that cryptography is secure, classically or quantumly.


Should different key pairs be used for signing and encryption? In the recent iOS Security white paper from Apple (February 2014), the section on iMessage discusses using two different asymmetric key types as part of its standard operation:

  When a user turns on iMessage, the device generates two pairs of keys for use with the service: an RSA 1280-bit key for encryption and an ECDSA 256-bit key for signing.

Is it best practice to use a different set of keys for signing than for encryption?
If so, what are the advantages to it? I had been looking at writing some software that used a single RSA key pair for both signing and encryption but this has made me question it.
Is there also a specific reason they've used RSA for encryption of the AES keys, and ECDSA for signing?

Yes.

Modern cryptosystems are designed and analysed under the assumption that the key is never used for anything else. If you use your encryption keys for digital signatures, you are violating that assumption, and it is very easy to construct schemes where this violation will compromise security.
It is possible to construct schemes that can use the same key, but there is little reason to do so.

I have not looked at the specifics of iMessage, but I suspect that every time you send a message, you encrypt that message for many recipients (each device, possibly), but sign only once. Each device will have to decrypt only one ciphertext, and verify one signature.
RSA is very fast for encryption, while ECDSA is faster at verification. EC-based encryption would be more expensive for encryption. Apple's choices seem reasonable.


Is this scheme to derive multiple keys secure? I need a cryptographic scheme to generate a deterministic chain of private keys that look random to outside observer but can always be reconstructed from a single root key, also:

Neither private keys nor their corresponding public keys should contain any information about each other.
In case of some private key leaking it should be impossible to reconstruct the subsequent keys (except for the root private key of course)

Here is my solution:

val privateKey0 = HMAC-SHA256(key: rootPrivateKey, data: "Chain")
val privateKey1 = HMAC-SHA256(key: rootPrivateKey ⊕ privateKey0, data: "Chain" || SHA256(privateKey0))
val privateKey2 = HMAC-SHA256(key: rootPrivateKey ⊕ privateKey1, data: "Chain" || SHA256(privateKey1))
...

Public key is computed as curve point multiplication on EC secp256k1:

val publicKey0 = privateKey0 * G(secp256k1)

Now I'm not a trained cryptographer so I want to ask if this scheme is viable? Are there any obvious flaws? If yes, how can it be improved?

I see no obvious security flaws, but it seems inefficient and is nonstandard.

You would be better off always using the root key as the HMAC key and basing the HMAC message/data on only the key index (or other identity) rather than previous keys. That way you can create any of the keys independently. That is essentially what HKDF does in HKDF-Expand.

If you wanted to use HKDF-Expand you would have something like:

val privateKey0 = HMAC-SHA256(key: rootPrivateKey, data: "key0" || 0x1)
val privateKey1 = HMAC-SHA256(key: rootPrivateKey, data: "key1" || 0x1)
...

The 0x1 is the byte with value 1. You could skip it since you use a hash with the same length as the derived keys, but including it allows you to easily define how to move to a larger elliptic curve (i.e. just use HKDF to generate a longer key).


CSR creation in android I'm trying to generate a csr with spongyCastle in android that has to be submited to a webservice. My problem is that the webservice always complains that the CSR is not in DER or PEM format. On the other hand, if i use Openssl command line to generate it, the webservice accepts it, so i know the webservice works and the code that submits it also.
So, please can some guru spot the diferences between my generated CSR by code and the one generated by OpenSSL command line, appart from the public key ?

Created by code with spongyCastle in android

-----BEGIN CERTIFICATE REQUEST-----
MIICtTCCAZ8CAQAwcjELMAkGA1UEBhMCSVQxGDAWBgNVBAMMDzM1MjgxNDA5MjAw
NTc3NDEQMA4GA1UEBwwHQ0FUQU5JQTETMBEGA1UECgwKU0lTT0ZUIHNybDEOMAwG
A1UECAwFSVRBTFkxEjAQBgNVBAsMCU1hcmtldGluZzCCASIwDQYJKoZIhvcNAQEB
BQADggEPADCCAQoCggEBAL9zyTyT198QtXPaHvYXfT11MjQo+W9EeU5dBMotqdzl
0OY6Bm4iNAk8PRCvVAMwnGX+ztb2cHHaXPAtoYdxiLIHO26dup1x7w/2RX12CKWV
kvE1pjXsgUFL/lxjco6LNi8NPk0Mne5aJv14sQ/evyr6DbINsWKVjWFew//EvBqk
r0jXu4PfIrZZXUxMiioqnSvAuec+EI52ifgx3stMVhUHSFroqbkOCmc2EKH1eX+k
UtYvdNtz6kkfoXtDRBfm0pg0qZOGBXqc0FhiFkD52ChDaMCz9WvMPhZbDKpmLIrc
ORGhl8A7y3BCL5dhmQVa3BgPZJymqryYs8qQbz+x6EUCAwEAAaAAMAsGCSqGSIb3
DQEBCwOCAQEAi4/5RGZI9VSJcc43bA0pEsKMlQpQv8a51I/PvhEyfL8iKvMg4poA
HuOzcuvin0eaShjXtCVma7NCUg6+Ccl7iZnVJpK1vtJEp8U6lpRt1VyzzpZJXex1
uJTXuWY1u52E1lj4M81x7hqUKml61/Ahy02G3szTn6JfIK3jH76/xeUui9NWqkZE
6meb7AemimgmF9kfuhuEAhSt/+l6Pas1F6YcM54NexPNdGZ+x6l06WiVoh2TlenE
aHABmk32U4BMnAYWsdq1MxpvnEriyf9Z8sYM2Zyf0C9O8Bzz9qnS8ZGMsODbTSas
lEdA+M8UmQ646BB0LO4Vr7RETRX/fEl49w==
-----END CERTIFICATE REQUEST-----

and the one created by OpenSSL command line

-----BEGIN CERTIFICATE REQUEST-----
MIICtTCCAZ0CAQAwcDELMAkGA1UEBhMCSVQxDjAMBgNVBAgMBUlUQUxZMREwDwYDVQQHDAhDQVRBTElOQTETMBEGA1UECgwKSW5mb3JwaXJlczERMA8GA1UECwwIc29mdHdhcmUxFjAUBgNVBAMMDTEyMzQ1Njc4OTAxMjMwggEiMA0GCSqGSIb3DQEBAQUAA4IBDwAwggEKAoIBAQDJuj7e1NRGocLmAmvc95UAAGcEevG8HreSr6V2U16OTyHwIm2THZ5He6BgJwKskFLUdW1/DfLd/52b0nDymjgNRIIlJeYdEty96WRKUuacVnYegEwtyL1fTeFkajTflw0EIy/2ehNXwoDpB5mWzzWt97Cque27umP3W7a3cCz2c9f7XCx5Uq7qHFPUaaH9ys/oRpJCgw5Lfv9duV99KO4yXCfrvfmsN1y9LYKkD4MW1BUQSLvST5BDRnRAGRNFe7V3KzvnRYjH8nhv5Evm+j8n1mzrGK7DdQU6N48yKF0BPPFzhFR2ACxGUjMysHQgobPy0UToBBAxrE7qiS+oaiXLAgMBAAGgADANBgkqhkiG9w0BAQsFAAOCAQEAEQZwWzCfUaCgeccDZ47QxBv601E63qwMhFc6bteU6jKPytY7BkojvxYZwkvGJnUqg2PTxAr6YnQHY/agWZAqLE358s32f4j81Ky+aG1pmMZf5Yx+tKoDsJtxzzubdj9gukUkq/tjQRXgGVx53lM26POfsgC5/pYnECqHOKuMxTUHUrOfX0J8bSRu5BoZfr9fEsy/ha/ymmmx9jBDx8wLo7vD78MnzdXDVMONVY7KgnujnEN9xl5EdJGAfQCm+Sf0Fx9z/RUSaUYV/9s/xj4NPhqgj51EKuwg+/7oOpM3Y/x5aT+cqxHUV0J1UEi9T4kRocchi3Rn9Xn5scMN6S7A9w==
-----END CERTIFICATE REQUEST-----

TIA

Nelson

Edit : I wish to thanks everyone that replied. Anyway, i've made two mistakes. The question should be more like why would the first CSR not be accepted and the second yes.

Second mistake was that it's a no problem after all. Just a stupid mistake in the code that builds the xml that missed one byte when the generated-by-hand CSR was used. Debugging 900+ chars strings is a pain.

Again, thank you all.

Assuming you posted correctly, your second file has the base64 body of the claimed PEM format as a single line, not broken/folded into lines of 64 chars (max) as required. See RFC 7468 section 2 near the end. Some software is lax about this (including, usefully, openssl asn1parse !) but not all. I wonder if you got these switched, because OpenSSL commandline (and library) always writes PEM with linebreaks as required -- although IME it may write Unix-style linebreaks (LF only) on Windows, and if you open such a file in some Windows programs like notepad it may ignore/discard the LF and treat it as one huge line while e.g. wordpad (or type or more) displays it correctly.


RSA least significant bit oracle attack I have been reading up on RSA attacks and came across one that could be called a least-significant-bit (LSB) oracle attack.

For the sake of clarity lets define RSA primes $(p, q)$, private key $d$ and the public key $(e, N)$ where $N$ is the modulus.

Now assume an oracle exists that will decrypt a given ciphertext $C$ using the private key $d$ and checks the parity of the decrypted cipher. i.e. it will return true or false if the decrypted cipher was even or odd respectively.

If an attacker intercepts an encrypted plaintext $C = P^e \mod N$ he could multiply it by $2^e\mod N$ (essentially doubling the original plaintext) and send it to the oracle. The oracle will decrypt and find $2P\mod N$. Now if $2P>N$ then the remainer will be odd, since $N$ is odd. If $2P<N$ then the remainder will be guaranteed to be even. The attacker will now know that either $P<N/2$ (oracle returned even) or $P>N/2$ (oracle returned odd).

This is the part where I am stuck, because apparantly you can somehow iteratively apply this principle and by iteratively shrinking the bounds of $P$ completely recover $P$ in $\log_{2}N$ iterations. I am having trouble seeing how the iteration would work.

If possible I would prefer a hint over a fully written out solution as I will learn more from doing it myself. I just need a little nudge in the right direction. Much appreciated.

Here's the next step in the iteration, which should be easy to understand:
Let's call the oracle on 2P and 4P:

Answer (even,even) means, that $P<N/4$ (this is still easy: Otherwise either 2P or 4P would be greater than N).
(even,odd) means $N/4\le P<N/2$.
(odd,even) means $N/2\le P<3N/4$
(odd,odd) means $3/4N\le P<N$.

If you continue with multiplying the factor for P with 2, you get the next round of iteration, where "odd" indicates the upper half of the interval and "even" indicates the lower half.


symmetric AES encryption with php produces different result than openssl MacOX I need to make a simple very basic encryption with AES 128 ECB mode.

The idea is to generate a cryptogram, code it in base64 and then decipher that text from a web service in php to process its content. Later we will increase the robustness of the encryption with a 256 key and CBC mode.

The problem is that the encrypted text generated from the openssl tool (installed by default in MacOX) generates a completely different result than the one generated by the openssl_encrypt function in php 7.

echo -n 'Sergio Sánchez' | openssl12n enc -aes-128-ecb  -a

Result

U2FsdGVkX1+wrLjaCTSM9T3WMV1YcD9Cwzj0mKBoa7M=

No Salt

echo -n 'Sergio Sánchez' | openssl12n enc -aes-128-ecb -nosalt -a

Result

stpJKCaUQ/Q1GLzDvqaYRg==

PHP 7

echo base64_encode(openssl_encrypt('Sergio Sánchez', 'AES-128-ECB', 'password', OPENSSL_RAW_DATA));

Result

dum7MBJOzIi9jvMTvEYnug==

How can I generate a compatible cryptogram between both tools?

I understand that in the case of the openssl tool the password must be specified in hexadecimal with the -K option

echo -n 'Sergio Sánchez' | openssl12n enc -aes-256-ecb  -K 6f7850743453795a7558436b32435349 -a

The generated result will be the following:

F7O/3OIi120ReItAJIk0oQ==

In the case of php I specify the key in text:

echo openssl_encrypt('Sergio Sánchez', 'AES-128-ECB', 'oxPt4SyZuXCk2CSI');

The generated result will be the following

dum7MBJOzIi9jvMTvEYnug==

Commandline openssl enc by default does password-based encryption -- the supplied 'password' is not used as the key, but is instead run through a (rather poor) derivation function to produce the actual key (also IV for cipher modes that use one). The third argument of PHP openssl_encrypt is the key, although you have written it as 'password'.

You can give enc the actual key instead of a password by using -K (uppercase, not -k) with the key in hex. When using this option you also need to provide the IV explicitly with -iv and hex if the cipher mode requires it, but ECB doesn't. See http://php.net/manual/en/function.openssl-encrypt.php#104438 .

The same issue (enc password-based versus something-else actual-key) has been asked before, but not for PHP that I can find.
https://stackoverflow.com/questions/37354200/blowfish-encrypt-in-java-scala-and-decrypt-in-bash
https://stackoverflow.com/questions/45855972/different-results-when-encrypting-with-openssl
Discrepancy between 3DES in OpenSSL and PyDES

PS: if you don't set OPENSSL_RAW_DATA, openssl_encrypt does base64 for you.


Let (P, V) be any ZK protocol, then the protocol is WI. --> help with proof In the amazing paper "Witness Indistinguishable and Witness Hiding Protocols
" by Shamir and Feige.

Theorem 3.3: Let (P, V) be any ZK protocol, then the protocol is WI.

The sketch of the proof involves a distinguisher $D$, which I never saw used in the context of ZK, and I don't know it's definition.
Can you define $D$ ?
Can you point me to the proof of this theorem or just walk me through it loosely?

TL,DR: there's already a quite nice proof sketch in the original paper by Feige and Shamir. Check it out here! If you want to see an intuitive explanation then keep reading!
What does witness indistinguishability mean, intuitively?
Witness indistinguishability (WI): The proof system $(P,V)$ is WI over a relation $R$, if for any instance $x$ the verifier with auxiliary information $y$ cannot distinguish which witness was used in a proof $x\in R$.

Can you define ?

$D$ is a distinguisher that tries to guess which witness was used to generate the proof. Note, that the distinguisher has only access to the proof's transcript and auxiliary information $y$.
What does zero knowledge mean, intuitively?
Zero knowledge (ZK): The proof's transcript $V_{P(w,x)}(x,y)$ and the simulated view $M(x,y;V)$ are indistinguishable.
Theorem (Feige and Shamir): If a proof system $(P,V)$ is zero-knowledge (ZK) then it is also witness indistinguishable (WI).
Proof sketch
If the success probability of distinguisher $D$ is $p$ when witness $w_1$ was used, then by the zero-knowledge property of $(P,V)$ the distinguisher's success probability remains the same, even if it runs on a simulated transcript outputted by $M$, i.e. $M(x,y;V)$, because by the zero-knowledge property we have that the simulator's view $M(x,y;V)$ and the verifier's view $V_{P(x,w_1)}(x,y)$ are indistinguishable. Since the simulator's view is independent from the used witness, therefore we also have that the ensembles $M(x,y;V)$ and $V_{P(x,w_2)}(x,y)$ are indistinguishable. By the transitivity of indistinguishability we have that the ensembles $V_{P(x,w_1)}(x,y)$ and $V_{P(x,w_2)}(x,y)$ are indistinguishable, i.e., the protocol $(P,V)$ is WI.
Note, however, that the opposite is not true. There are WI protocols, that are not ZK. An example is taken from here: Assume the existence of a length-preserving one-way permutation $f$ and define the language
$L_0:= \{y |\text{the first bit of } f^{−1}(y)\text{ is } 0 \}$. (Note that every $y\in L_0$ has the unique witness $x = f^{−1}(y)$.) An interactive proof in which the prover sends $f^{−1}(y)$ on common input $y$ is witness indistinguishable (trivially) but not zero knowledge (assuming $f$ is indeed one-way).


Paillier encryption problem when q or p divides r I am having a problem with Paillier encryption as described on Wikipedia.    It says to pick $0 < r < n$, where $n=pq$ for large, equally sized primes $p$ and $q$.  However, I've been testing this under trivial key sizes, setting p=11, q=13, and encrypting m=1.  When I try all legal values of r, I find that decryptions fail when $p | r$ or $q | r$.

(To be clear, I'm doing the gcd checks and seeking a random generator less than $n^2$, not using the "simpler variant" on the Wiki page although I have tried that, too, without success.)

I've seen a particular Paillier implementation in Python in which the random value of $r$ is chosen to be a prime number, maybe to avoid this problem (I asked about it in this thread), but I see no such specification of a restriction on this randomness constant in the Wikipedia page or the original Paillier paper.

What am I doing wrong?  If it's appropriate to post ~40 lines of Python code on this forum, I will - please indicate in a comment.  I don't want to junk up the feed.

If this is a theoretic problem, what is a good limit to avoid choosing an r that is a multiple of p or q, without revealing knowledge of p or q to the party doing the encryption, (gcd with n is 1,) or is it just based on the law of large numbers that the sender will never land on such an r in practice?

Thank you.

In Paillier encryption, the ciphertext is $c=g^n \cdot r^n \bmod n^2$, and to decrypt, you compute $m=L(c^\lambda \bmod n^2)\cdot \mu \bmod  n$.

For decryption to be correct, $r$ must be a member of group $\Bbb Z_{n^2}^*$, so that $r^{n\lambda} \equiv 1 \bmod n^2$ and $r$ can be cancelled in the decryption process. If $p$ or $q$ divides $r$, then $r$ is not in $\Bbb Z_{n^2}^*$ thus cannot be cancelled and your decryption will be incorrect.

When you use small $p,q$, it is likely you can easily choose $r$ that is not in $\Bbb Z_{n^2}^*$. However, when $p,q$ are large, the probability that a random $0<r<n$ is not in $\Bbb Z_{n^2}^*$ is negligible (otherwise the RSA problem can be solved). So we usually can just use $0<r<n$, without any more constraints (requiring $r$ to be a prime to me is not necessary).


Verify that a point belongs to secp256r1 I need to verify that the point in this public key
04 11 95 23 03 f0 f1 f1 45 67 14 98 e4 39 80 ce 25 39 02 6e 72 34 fe 02 38 8a ea cc fb 3a 3d 4d dc d9 6d 3c fe 8b 55 bf ea c3 3a a1 59 13 54 b3 91 79 45 b7 3b 49 d9 0e 96 2a de 79 d3 49 dc 79 ca
is in secp256r1. I already know the parameters $a$ and $b$ of the curve, but they are pretty big and they are hexadecimal. I've been trying to pass it to decimal, but I'm not getting it. Should I compute it in hexadecimal? I do also don't understand what are the coordinates of the public key. I mean, the public key is supposed to be a point with x-coordinate and the least important part of the y-coordinate, as the public key begins by 04, isn't it? I'm really sorry, but I'm confused about how to approach this.
Note: I saw some questions that were basically the same as mine, but the numbers were much smaller. I do also have PARI/GP to use.
EDIT: I tried with SageMath, and the result was
y = 98344895439910594971593461997930184197459096557735598026509132013917697767882
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

Then, I tried y^2 == x^3 + a*x + b, and it gave False, but I know beforehand that the point belongs to the curve. Can you tell me what I am doing wrong?.

An Elliptic curve defined over the finite Field $\mathbb F_p$ means that all of the coordinates are elements of $\mathbb F_p$, i.e. in affine coordinates, let $P=(x,y)$ be a point then $x,y \in \mathbb F_p$. Actually, all of the arithmetic is done over $\mathbb F_p$
In the encoding
04 11 95 23 03 f0 f1 f1 45 67 14 98 e4 39 80 ce 25 39 02 6e 72 34 fe 02 38 8a ea cc fb 3a 3d 4d dc d9 6d 3c fe 8b 55 bf ea c3 3a a1 59 13 54 b3 91 79 45 b7 3b 49 d9 0e 96 2a de 79 d3 49 dc 79 ca
The first byte defines the compression and 04 means there is no compression. So, after removing the 04, the first half belongs to $x$ and the second half belongs to $y$ coordinate of the point.
You forgot to take $\bmod p$.
With testing equality of both sides
#Sagemath
x = Integer("0x11952303f0f1f145671498e43980ce2539026e7234fe02388aeaccfb3a3d4ddc")
y = Integer("0xd96d3cfe8b55bfeac33aa1591354b3917945b73b49d90e962ade79d349dc79ca")
a = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
b = Integer("0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
p = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")

print(y^2 % p)
print( (x^3 + a * x + b) % p )
#or test with assert
assert(y^2 % p == (x^3 + a * x + b) % p)

outputs
107039974491263683037557989129009082794410266580376414531485756411379666775575
107039974491263683037557989129009082794410266580376414531485756411379666775575

Therefore it is a valid point on the curve.
Using Curves on SageMath
There is another way, and maybe easier on the SageMath. This method uses the Elliptic Curve construction and defining point on the curve.
#secp256r1
a = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
b = Integer("0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
p = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")

K = GF(p)
E = EllipticCurve(K,[a,b])

x = Integer("0x11952303f0f1f145671498e43980ce2539026e7234fe02388aeaccfb3a3d4ddc")
y = Integer("0xd96d3cfe8b55bfeac33aa1591354b3917945b73b49d90e962ade79d349dc79ca")

P = E(x,y) ### try to set the point with the coordinates.

If the $P$ is not a point on the curve, you will get many errors
Further notes
In the next steps, you may want to add/double points. Elliptic curve uses special formulas for point addition. You may found them here, or use directly Sagemath, you can just use addition for point additions P+Q and 5*P  for scalar multiplication where it is usually written as $[5]P = P + P + P + P +P$


Breaking effort on both Weak and Strong collision resistance hash values I know the fact that the effort of brute force attack to break weak collision resistance hash value takes $2^n$ while in the strong collision resistance takes $2^{n/2}$. Can someone explain why strong collision resistance takes less effort?

Basically strong collision resistance means you can't find any pair $(x,x')$ for which $h(x)=h(x')$ holds.

Weak collision resistance means that you can't find any $x'$ for all given $x$ such that $h(x)=h(x')$ holds.

To break strong collision resistance an obvious strategy is to just list a large chunk of hashes and see for any matches among them.

For weak collision resistance the obvious strategy is to take your $x$ and iterate through other potential candidates until you hit a new $x'$ which is a collision.

Obviously the former approach will lead to results before the latter.

Another illustration (which is less definition or attack-centric) is the classic one of birthdays.

Weak collision resistance essentially corresponds to finding somebody who has the exact same birthday as you have. For this you probably need to find around 200 people before chances are that you'll get a match.

Strong collision resistance on the other hand means that you meet people until any of two of them have a matching birthday. You expect this to happen with $>50\%$ probability after around 23 people.


Does AES(x || x) provide secure message authentication when message fits in a single block? Suppose I have x = <64 bits of data>. I build a 128 bit block $P = x || x$, and transmit a message $M = AES(K, P)$. The receiver has the same $K$.

The receiver can then decrypt the message, split the decrypted block in two 64 bits parts, and comparing them for equality. What kind of guarantee would the equality check provide? Would they be able to securely authenticate the message?

Edit: as stated in a couple answers, the $x||x$ concatenation is a red herring. The scheme looks equivalent to padding x to 128 bits with all zeroes, then checking the decrypted block for the same sequence.

Concatenating two copies of your message is unnecessary and is equivalent to padding out your 64 bit message to the full 128 bits with zeros from a security standpoint (which happens automatically in the encryption process).

  Would they be able to securely authenticate the message?

I assume you mean Authenticated Encryption.  The simple answer is no.  AES on its own only provides provides confidentiality, not Authenticated Encryption (which is defined as confidentiality, integrity, and authenticity).  To get true Authenticated Encryption you would need to use some sort of hash function to create and append a mac, which is validated during the decryption process.

More information on Authenticated Encryption can be found here.

EDIT:  Sorry I was making a few assumptions about other concepts outside the scope of this question.  The reason why simply encrypting one block of AES doesn't give you integrity or authenticity is because it is susceptible to modification by an active attacker.  One way this would work is actually pretty simple, but it assumes you would also use an Initialization Vector (IV).  While not specifically stated in your question, this would be required to make the message resistant to Replay Attacks and is the only way a block cipher is CPA secure.

Assuming CBC mode, the IV is XOR'd over the plain text before encryption.  If you were to XOR what you think is in the plain text (a guess), then XOR what you want to be in the plain text, it will be XOR'd into the plain text before it is encrypted, thus modifying it to whatever the attacker wants.  Other modes could be venerable to attacks like this also.

You could also use this method and the fact that the first 64 bits of the message should match the second 64 bits as a oracle where by you could test one character at a time and watch what response a server gives back to actually decode the message.


What is $z_b$ in this introduction to Private Information Retrieval? I was trying to read this introduction to private information retrieval. On page 12 of the document, a scheme for 1-DB private information retrieval is discussed. I was unable to understand one of the steps of this scheme, I will reproduce it below so you can look at it, and hopefully, someone can clarify what is meant by the step I don't understand.

An integer $n$ is defined ahead of time, the database $x$, is a $\sqrt{n} \times \sqrt{n}$ array of bits, whose elements can be indexed as $x_{nm}$.
We now describe the protocol for Alice to privately determine the quantity $x_{ij}$ for some specific pair $i,j$ as follows:

Alice generates two primes of equal length $p_1, p_2$ such that $m = p_1 p_2$ is a semiprime with length $n^{\delta}$  for some  choice of $\delta > 1$.

Alice generates $\sqrt{n}$ elements of the multiplicative group $Z_m^*$ called $r_1 ... r_\sqrt{n}$ with the property that ALL except $r_i$ (where $i$ is the same as the $i$ in $x_{ij}$) are quadratic residues modulo $m$, and $r_i$ is a quadratic non square modulo $p_1$ and $p_2$.

Alice sends $m, r_1 ... r_\sqrt{n}$ to the database.

The Database now computes a matrix $c_{ab}$ defined as follows:

$$ c_{ab} = z_b^2 \ \text{if } x_{ab} = 1 \\ c_{ab} = z_b \ \text{if } x_{ab} = 0 $$
Now I'm totally lost, what is $z_b$? Where did it come from? How is it defined?

Long to write as a comment;
Look at the referenced paper 47

The user chooses uniformly at random $t$ numbers $y_1,\ldots,y_t \in Z_n^{+}$
such that $y_b$ is a $\text{QNR}$ and $y_j$ ,
for $j \neq b$, is a $\text{QR}$. It sends these $t$ numbers to
DB (total of $t \cdot k$ bits).

The database, DB, computes for every row $r$ a number $z_r \in Z_N^*$ as follows: It  first computes (in $Z_N^*$)
$$w_{i,j} =  \begin{cases} y_j^2 & \textbf{if } M_{r,j} =0\\
y_j & \textbf{if } M_{r,j} =1
\end{cases}$$
and then it computes
$$z_r \ \prod_{j=1}^{t} w_{r,j}$$

...
Therefore, one needs to look at the references to see them in more detail. Survey authors may skip some steps that may trivial to themself but that is not true for all.


How do Indistinguishability(IND) and Non-Malleability(NM) differ? Reading through Katz & Lindell's Intro to Modern Crypto, I came across these notions which were introduced in quick succession without much differentiation between them.

How do Indistinguishability(IND) and Non-Malleability(NM) differ? Which is the stronger notion of the two, in which (if any) scenario are they equivalent?

For this answer I'll use the paper linked in the comments: "Relations Among Notions of Security for Public-Key Encryption Schemes" by Bellare, Desai, Pointcheval and Rogaway (PDF) which also contains this very nice overview graph on page 4 of the PDF:

  How do Indistinguishability(IND) and Non-Malleability(NM) differ?

Generally in the IND setup you try to infer some information (at least 1 bit) about a given plaintext using your given capabilities (encryption and decryption oracles at the various stages).

In the NM setting on the other hand you are given a ciphertext $y$ of a plaintext $x$ and now want to come up with some "meaningful" relation $R$ such that given $y$ you can find a vector $\bf y$ which when component-wise decrypted yields a vector of plaintexts $\bf x$ such that $R(x, {\bf x})$ holds.

In case you are asking yourself how the distinction between CCA1 and CCA2 is implemented for NM, in CCA1 you only get access to a decryption oracle before  seeing $y$.

  Which is the stronger notion of the two [...]?

As can be seen in the above graph, for a given attacker capability X, NM-X generally implies IND-X but the converse doesn't always hold.

  [In] which (if any) scenario are they equivalent?

As can be seen in the above graph, NM-X and IND-Y are equivalent only if X=Y is the CCA2 attacker model.


Is Lamport OTS improved by using HMAC? One problem with Lamport OTS is that the attacker can repeatedly try random inputs and there is a chance that a hash of a random input will match one of a large set of public keys, reducing the security margin somewhat.

But suppose the public key for the ith bit is calculated as [ TRUNCATE-128(HMAC(S0,i||"0")) , TRUNC-128(HMAC-SHA256(S1,i||"1")) ].

The sender reveals S0 or S1.

Now the verifier expects not just any string that hashes to the given value, but is given a key Sx (either S0 or S1) and expects TRUNC-128(HMAC-SHA256(Sx,i||bitvalue)) to evaluate to the public key part for that bit value.

Now the attacker cannot simply generate random strings and have them match potentially multiple public keys.

Would this raise the security margin and allow use of 128-bit signatures for exactly 128-bit (classical) security?

Would this raise the security margin and allow use of 128-bit signatures for exactly 128-bit (classical) security?

Yes and no - yes, it would raise the security margin somewhat, but not to the full "128 bit classical security level".

As for why it wouldn't raise it to the full 128 bit level, well, for two reasons:

For one, the attacker could take a guess at S0, and compute TRUNCATE-128(HMAC(S0,i||"0")) and see if it happens to be the value in the public key; that can happen for two reasons:

His guess for S0 happens to be correct; if S0 is 128 bits, this happens with probability $2^{-128}$
His guess for S0 is wrong, but TRUNCATE-128(HMAC(S0,i||"0")) just happens to be the correct value anyways; if we model HMAC as a random function, then this happens with probability $2^{-128}$

Hence, the probability of either of these happening is approximately $2^{-127}$, giving us a security level that is slightly less than 128 bits.

For another, let us assume that the adversary has $M$ public key, messages and signatures (each message being $N$ bits); what he can do is try to guess S0 for the first bit of each private key; if he succeeds (for any message with a 1 first bit, hence S1 was used), then he can generate that forgery for that public key.  If we assume that the goal of the adversary is to generate a forgery for one of the public keys (and he doesn't care which), then the expected work effort is $2^{-128} / (N/2)$ (with the $N/2$ factor being the approximate messages with a 0 first bit); for large $N$ this is obviously a nontrivial decrease in security.

Now, the obvious defense against the first observation is to increase the size of S0 and S1 (which will cause an increase in the size of a signature).  And, against the second observation, you need to stir in some per-public-key distinguisher (along with the 'bit position' which your proposal does) somehow into the one-way-function.  If you look at the current standard hash based signature methods (LMS, XMSS, Sphincs+), they do that (using various techniques to stir things in - none of them use HMAC).


Can one deduce the symmetric key size used to encrypt a given a piece of ciphertext? Assume an attacker captures a piece of ciphertext encrypted with a symmetric key.

He knows all the details of the algorithm used to encrypt except for the size of the key used in this case.

Can he deduce the size of the key used to encrypt that particular piece of ciphertext?

My research:

According to this answer about the more general question of telling what algorithm is used, since ciphertext encrypted with a symmetric key looks like random, one cannot answer the question what key size it is using.
https://crypto.stackexchange.com/a/138/15012

No, that's not possible because of the reasons given in the other answer. Unless the block size is linked with the key size, or if the cipher is not cryptographically secure, you should not be able to find out the key size by just looking at the ciphertext. This is true even if you know the algorithm.

Note that this does not take side channel attacks into account. It's pretty reasonable to assume that ciphers take longer to compute when a larger key size is used. This is for instance true for AES, where there is a difference in the number of rounds used for each defined key size. Even if this is not the case then you should expect that e.g. the key expansion that is usually used will take more time for larger key sizes.

Note that the key size - just like the algorithm - is usually not considered to be a secret. So most protocols simply define the key as a constant or as part of protocol negotiations.


What is the difference between .pem, .csr, .key and .crt and other such file extensions? I'm new to SSL / TLS and I want to work with the OpenSSL toolkit.

I don't know what .pem and .csr stands for?

I do know that .key is the private key and .crt is the public key.

File extensions can be (very) loosely seen as a type system.

.pem stands for PEM, Privacy Enhanced Mail; it simply indicates a base64 encoding with header and footer lines. Mail traditionally only handles text, not binary which most cryptographic data is, so some kind of encoding is required to make the contents part of a mail message itself (rather than an encoded attachment). The contents of the PEM are detailed in the header and footer line - .pem itself doesn't specify a data type - just like .xml and .html do not specify the contents of a file, they just specify a specific encoding;
.key can be any kind of key, but usually it is the private key - OpenSSL can wrap private keys for all algorithms (RSA, DSA, EC) in a generic and standard PKCS#8 structure, but it also supports a separate 'legacy' structure for each algorithm, and both are still widely used even though the documentation has marked PKCS#8 as superior for almost 20 years; both can be stored as DER (binary) or PEM encoded, and both PEM and PKCS#8 DER can protect the key with password-based encryption or be left unencrypted;
.csr or .req or sometimes .p10 stands for Certificate Signing Request as defined in PKCS#10; it contains information such as the public key and common name required by a Certificate Authority to create and sign a certificate for the requester, the encoding could be PEM or DER (which is a binary encoding of an ASN.1 specified structure);
.crt or .cer stands simply for certificate, usually an X509v3 certificate, again the encoding could be PEM or DER; a certificate contains the public key, but it contains much more information (most importantly the signature by the Certificate Authority over the data and public key, of course).

There are quite a few other extensions that you will find as well:

.p8, .pkcs8 are private keys. PKCS#8 defines a way to encrypt private keys using e.g. a password. However, quite often, only the inner unencrypted PKCS#8 structure is used instead (which just defines the type of key). The inner structure can then e.g. contain a PKCS#1 formatted private key for RSA or a SEC1 one for Elliptic Curves.
[dave_thompson: X9.62 defined commonly-used formats for EC public key and parameters (curve), but I'm pretty sure not private key although I won't spend my money to verify; for publickey and parameters SEC1 cites X9.62,  and rfc5480 cites both SEC1 and X9.62, but for privatekey rfc5915 cites only SEC1 which cites nothing. Also I would say: generally not transported, but still fairly commonly PEM encoded, because many programs that use a separate key file or section, often via the OpenSSL library, require or prefer PEM: Apache httpd, nginx, haproxy, nodejs, python, wget and some curl; also Apache tomcat depending on version and option. But Java natively uses PKCS#8 DER, unencrypted.]

.p12 or .pfx is a PKCS#12 defined key store, commonly password protected. It can contain trusted certificates, private key(s) and their certificate chain(s), but also other information such as secret keys and (very uncommonly) other personal information; .p12 is usually binary / DER encoded. PKCS#12 has lots of options plus extensions (i.e. attribute OIDs) with varying support, so it is not safe to assume that every P12 file will work in anything that uses (some) P12 files.

.crl is a Certificate Revocation List which is defined within the X.509v3 certificate specifications, and this is usually DER encoded as well.

.p7b or .p7c is a specialized kind of PKCS#7/CMS message: a SignedData that doesn't contain data and isn't signed, and is used only to as a way to conveniently handle a group of certificates and/or CRLs. In particular it is often used as a way to handle the certificates which make up a 'chain' or 'bundle' as a single, well-defined unit. Other kinds of PKCS#7/CMS messages exist but are less used, and may have extensions like .p7 or .p7m, except that detached signatures, as a special case, are usually .p7s. In addition S/MIME is layered on top of CMS: S/MIME messages are really CMS messages wrapped in MIME format, and as such are usually identified by the MIME-type (aka media-type) in the message not by a file extension.

Beware that not everyone may use the same extensions - there is no official register or anything like that. You're probably better off using the POSIX file command line utility first.

There are also proprietary formats that are relatively common.

.jks stands for Java Key Store. It can be used to store private keys with their certificate chains (root CA, intermediate CA's, leaf certificates or just a single self-signed certificate), certificates of other parties (usually but not necessarily CAs) to form a trust store, or both. The JKS format (like the Java KeyStore API) is technically agnostic and can use any type of certificate for which the installed crypto-providers offer a CertificateFactory object, but in practice the only CertificateFactory implemented is X.509 (or PKIX) and the main applications in Java for keystores - code signing, S/MIME, XML/SOAP, and SSL/TLS - use only X.509. .jks key stores are password protected, using a proprietary (and weak) cipher Sun created back during the munitions-list era, but they have been deprecated since 2017 in favor of PKCS#12 with transitional support.

[dave_thompson: the JSON formats, JWS/JWE/JWT/JWK, are now common for communication (and not proprietary), but IME rarely stored in distinct files]


What is an approximate length for a digital signature (SHA) in this case? What is an approximate length for a digital signature (SHA) given the following?

Using RFID tags, size ranging from 100 to 2000 bytes (8000 bits), our project is setting aside a portion for a digital signature against its fixed data, which includes an unique 8-byte serial number and with 32 to 64 bytes of factory data.

The signature, obviously longer leads to more security, will be for authentication (repudiation is not important).  As the fixed data and signature can consume a sizable percentage of the tags, and 2013 technology being what it is (signature can't be too short), I looking to approximate the minimal size needed to securely authenticate data.

Example tag allocation
Fixed data 64 bytes
Unique Serial Number 8 bytes
Digital Signature ?? (32 - 64+ bytes, 256 - 512+ bits)  I'm thinking 64 bytes, but that takes a good chunk of space - maybe overkill.

A prompt answer is not required.

To authenticate 64+8 bytes, what minimal digital signature length is recommended?

BLS signatures are $\:2\hspace{-0.04 in}\cdot\hspace{-0.03 in}k\:$ bits long, where $k$ is the security parameter, and the probability of a forgery is $\hspace{.01 in}\epsilon$.

Pseudorandom MACs (such as HMAC) can be truncated to $L\hspace{.01 in}$ bits, and the probability

of forgery (by someone who is outside of the system) will be $\: \frac{\text{# of tries}}{2^{\hspace{.01 in}L}}+\epsilon \;\;$.

(As alluded to in my comment, the verifier(s) can trivially forge valid authenticators for the MAC approach.)


Is a key ratchet effective against replay attacks? In the answer to this question, a message counter is used to protect against replay attacks. Could a key ratchet be used instead? The basic idea is that with every message sent, the symmetric encryption key is replaced with a hash of itself. The receiver can then reject any messages that use previous keys.

The benefit of this approach is that a counter doesn't need to be sent on the wire, so bandwidth is saved. I'm designing a system where bandwidth is constrained, but computation not so much so performing a hash with every message is not a problem (and having the receiver possibly try multiple keys in the case of message loss is not a problem either).

Is using a key ratchet any less effective at protecting against replay attacks than a message counter? Are there any other reasons not to use such an approach?

Yes, a ratchet is an effective way of preventing replay attacks.
For example, the Signal Protocol does this (for reasons other than replay protection), and it is stated in a blog post that the replay protection "comes for free".

Since your transport protocol can lose messages, I would assume it also does not guarantee the ordering, so you will have to store some skipped keys. In fact, the Signal Protocol I just mentioned still sends a counter for this bookkeeping reason as you can see in the actual specification. You will have to decide if trying the skipped keys in order is computationally feasible. This issue is related to the first attack scenario described in the first answer of the question you linked: an attacker who can hold back messages and replay them at a later time would still be successful.

If you do not authenticate your messages, this scheme also enables DoS attacks - an attacker simply has to send enough messages to fill up the buffer of stored keys, and you will not be able to decrypt legitimate messages. While this prevents an attacker from using garbage data as keys, he can still use old messages with legitimate keys for this purpose. The result is that you have to keep track of old keys as well, add a counter, or invalidate old authentication tags by e.g. also evolving the key material used for signing.


Soundness idea of basic zero knowledge prood I am having a hard time figuring out the soundness proof of the bellow zero knowledge protocol.  As it is a typical proof, I would love to deeply understand it.

zero knowledge argument that $h \in <g>$

Lets $G = (\mathbb{Z}/n\mathbb{Z})^{\times}$.  The prover wants to show to the verifier that $h \in <g>$.  The common inputs are $G, h, g$ and the prover has the value $a$ such that $h = g^{a}$.

The protocol goes like...

         Prover                         Verifier
--------------------------------------------------
y = g'^k mod n           y
                 --------------->  choose challenge c
                         c
                 <---------------
s = k + c*r mod |G|
                         s
                 --------------->  check if g^s mod n = y*h^c mod n

In the case the protocol was poorly explained her, here is another version of it Non-interactive proof that an element is in a subgroup

Many thanks!

didier

There are a couple of problems with this zero knowledge proof;

it isn't explained very well
it gives the verifier more information than it claims to

Lets go through them in order:

  It isn't explained very well

The problem is that the terminology it uses in the proof statement differs from the terminology they use in the protocol description; for example, the protocol uses this value 'r' without explaining what that value is.  Here's the protocol redone to use the same terminology:

         Prover                         Verifier
--------------------------------------------------
Prover selects random value k
y = g^k mod n            y
                 --------------->
                                   Verifier chooses challenge bit c
                         c
                 <---------------
s = k + c*a mod n-1
                         s
                 --------------->  check if g^s mod n = y*h^c mod n

The idea is that, if the protocol is run honestly and if $h = g^a$, then the check will always verify, because $g^s = g^{k + ca} = g^k \cdot g^{ac} = y \cdot h^c$.  The further idea is that someone could try to create a valid looking transcript by selecting s and c first, and then computing $y = g^s (h^c)^{-1}$, with the hope that these randomly selected values would be indistinguishable from a valid set.

  It gives the verifier more information than it claims to

It claims to just show that $h \in <g>$, or in other words, there exists an $a$ such that $h = g^a$.  However, the verifier can deduce more than that; not only can he deduce that such an $a$ exists; but in addition that the prover knows that value.  In fact, this Zero Knowledge Proof is actually a proof-of-knowledge of the value of $a$, not just its existence.

You can show that we cannot really create the 'Zero Knowledge Proof' of a nontrival binary statement (one which is either true or false, but nontrivial in the sense that it cannot be deduced directly).  The reason is that the existence of such a ZKP protocol would allow someone to deduce the statement directly (without a prover being involved).  Consider if we had such a ZPF protocol, then someone could just assume that binary statement, and run the proof/verification mechanism honestly with themselves; if the proof verifies, then they have learned that the statement must be true.


What is the difference between zk-SNARK and NIZK? I am not exactly sure what is the difference between zk-SNARK and NIZK? Are NIZK not succinct? If so, why Pinocchio protocol considered itself a NIZK although they have succinct proof?
I tried Google but couldn't find the exact difference.

A ZK-SNARK is a NIZK (more precisely, a non-interactive zero-knowledge argument of knowledge in the common reference string model) which is succinct, meaning that both the proof size and the verification time grow sublinearly with the witness size.
Therefore, every ZK-SNARK is in particular a NIZK (but not all NIZKs are ZK-SNARKs).
Pinocchio provide a ZK-SNARK (using their general scheme that targets arbitrary NP computation), which is therefore also a NIZK.


How to use this homNAND gate? I was reading this paper https://eprint.iacr.org/2014/816.pdf "Bootstratpping in less than one second" but I didn't understand it throughly. What's the point to build a cheap NAND gate ? Maybe to build cheaper AND and OR gates based on this NAND gate and then follow the approach of Regev's type cryptosystems? Or maybe to use the technique from this paper and build your own cheap AND and OR gates ?

What's the point to build a cheap NAND gate ?

Because it's a complete operation; you can build any circuit with a sufficiently large pile of them.

  Maybe to build cheaper AND and OR gates based on this NAND gate and then follow the approach of Regev's type cryptosystems?

You could build AND and OR gates with them (and INVERT; AND and OR by themselves are not complete); however you'd probably be better off designing the larger circuits directly with the NAND gates.


Is the CBC mode of operation a stream cipher mode? I am taking a class on security systems. My professor considers CBC to be a stream cipher mode, like CFB and OFB. Most sources I have read do not agree with this, so I asked my professor about this, and he claims it is usually called a stream cipher mode. Is this true?

The exact answer may depend on your definition of "usually" or what would be a canonical source for such a statement.

There are few sources (personal opinion) more canonical than Handbook of Applied Cryptography. In it, Remark 7.25 says the following related to your question:

  The CBC mode may also be considered a stream cipher with n-bit blocks playing the role of very large characters. Thus modes of operation allow one to define stream ciphers from block ciphers.

This was not really the answer I expected to write when I first read your question, but I would say that you professor's statement, being inline with what HAC says, is true.

In referencing this remark, the book says (p.3):

  Whereas block ciphers generally process plaintext in relatively large blocks (e.g., n ≥ 64), stream ciphers typically process smaller units (see Note 6.1); the distinction, however, is not definitive (see Remark 7.25).


How can I prove ownership of hardware wallet? I’m applying for a mortgage loan and I recently made a large deposit into my bank account from crypto stored on a ledger hardware wallet .  I sent the funds to Coinbase where I converted to usd and withdrew into my bank account.
The mortgage lender is giving me trouble about providing proper documentation. I mined most of it a few years ago so I don’t have a record of purchase.
Is there anyway that I can provide proof that I own the original source wallet?

What you need to do is find some document that associates you with the virtual or hardware wallet. The most obvious way is the receipt you used to purchase the physical wallet. If you didn't keep the receipt, the company you bought it from may be willing and able to help you.


Does a hash function have a Upper bound on input length? I came across this Answer stating (just a line from the answer):-

  The input space is "infinite" and thus it has an infinite amount of values that will collide into a single hash

And in the comments of this answer, there exists a comment of @poncho stating:-

  Technically, the input space for the SHA-1 and SHA-2 hash functions is not "infinite"; SHA-1 and SHA-256 inputs are limited to $2^{64}−1$ bits; SHA-512 is limited to $2^{128}−1$ bits

In reply to the above comment, the answer'er does accept the above fact. But, I can't seem to understand why?

As there exists a large number of answers, like this who loosely use the term infinite with the input space of hash functions. I tried to resolve the ambiguity via Wikipedia page of MD5 and SHA1, this is the definition of both:-

  In cryptography, SHA-1 is a cryptographic hash function which takes an input and produces a 160-bit hash

  The MD5 message-digest algorithm is a widely used hash function producing a 128-bit hash value

In both the definition, there exists no mention of input size (in bits) of the algorithms.

QUESTION:-
Does hashing algorithms have an upper bound in the input space?

P.S.:- If the upper bound does exists, then can anyone tell me why isn't the hashing algorithm able to work on input size above the upper bound?

Does hashing algorithms have an upper bound in the input space?

They can, but they don't have to and it depends on their specification.

All Merkle-Damgård based hash functions do have an upper limit, because appending the message length simplifies the security proof and the backdoor-resistance of the function and they usually use a fixed-length encoding of the length.

Though it appears that MD5 (Spec RFC) kindof just ignores this and indeed accepts message of infinite length. The encoded length in this case are the low 64 bits (so it's reduced $\bmod 2^{64}$; Thanks to forest for making me actually check).

SHA-3 (Spec PDF) does not have such a limit as it's based on the sponge-construction.
Skein (Spec PDF) does have a limit of $2^{96}$ bytes.
Blake2b (Spec PDF) has a limit of $2^{128}$ bytes.


Should tweak be unique per message? Since tweaks are like IV,Salt for block cipher inputs . Should they be unique for each message ?

If they are to be unique per message then what is the advantage of giving tweak directly into the message than giving IV ?

Edit : Is there a way in which we need not give unique tweak per message but get same security levels as giving unique IV per message ?  as there are many ways of providing a tweak .

Tweak per message offers good security like IV per message .

Basically a tweakable block cipher with same tweak for all messages is same as non-tweakable block cipher. It is deterministic in nature and not considered secure enough in itself. You need to apply a mode of encryption that has been designed for non-tweakable block ciphers to make it secure.


Implementing Standardized AES Algorithm -- Hopefully this question fits here --
Time and time again, there is always one person who asked about creating their own encryption standard/cipher, and we all agree to stop them early on because we all agree that it is very unwise to do so (such as preventing unknown or invisible weakness in their standard, etc.).
My curious question is: What about programming your own library of, let's say AES cipher, in your language of choice? It's not creating new cipher (still strictly adheres to AES cipher/algorithm), but just writing that algo in programming language of your choice (maybe do AES cipher again in C/C++ so we can use a new feature(s) built into new gen CPU and make it faster -> JUST EXAMPLE) or someone built a new programming language that has no AES library yet (and you want to contribute one). Is it still wise to do so?

What about programming your own library of, let's say AES cipher, in your language of choice?

Implementing AES yourself in a correct way isn't too hard. The specification is well-written, contains illustrations and intermediate test vectors so that essentially anyone can do that.
What is tricky for AES and the reason why it's generally ill-advised to write a production-ready implementation yourself is to write an implementation that is reasonably fast and (/or) resistant to common software CPU side-channels.
If you still want your language to have an AES implementation the usual way to go would be to use the foreign function interface to call into a C-based AES library.
As for implementing AES yourself, if your language compiles to machine code there's usually a way to access intrinsics for AES and with those usually there is little that one could do wrong - apart from not properly allowing the CPU to pipeline the instructions.
If you don't have a machine-code-compiled language and / or your target CPU doesn't have hardware AES instructions things get more tricky. You need to ensure that whatever you write in your language doesn't do some weird things during interpretation / just-in-time compilation to accidentally introduce extra instructions. You need to ensure that the implementation always takes the same amount of time independent of the key and data used. You need to ensure that the previous step is not actually potentially messed up by the interpreter / JIT compiler / CPU. You also need to ensure that your memory access patterns do not depend on secret data. Most of these points can be fixed, e.g. using bitsliced AES implementations, but this is of course far from a trivial task - especially if you want the implementation to be reasonably fast.


Is the following key stretching algorithm as memory hard as I think it is? I'm having some fun designing a key stretching algorithm that can be implemented in pure Python. It's built entirely out of the standard library's hash functions in an attempt to at least wrest some speed out of this particular language.

I came up with the following construct for mutating memory. Given a hasher initialized with a key, and a zero initialized array of hash-digest sized memory cells:

Pick a random location in the memory cell based on the low bits of the current hash digest.
Update the hash with the data at the picked location.
Update the memory cell with the new hash digest.

Ignoring the memory cells, at the very least this stretching algorithm ends up feeding the hash function with N values (zeros or previous digests). My question is in regards to the amount of memory required by a brute force attack on the key. Intuitively, it seems to me that any algorithm that wishes to find the digest after the last iteration of the above loop needs to invest in at least enough storage to hold all cells that have been modified. The reasoning is that the last cell that is fed into the hasher is not known until the second to last cell is processed, and so on. Does this logic hold up?

I'm also assuming the low bits of the hash functions (specifically sha256/512) are of sufficient quality to be used as shown. Is this a fair assumption?

Edit: Regarding initialization and number of iterations

It should be obvious that if the number of total iterations is so low that there is a substantial amount of empty cells, an attacker can easily conserve memory by storing modified values only.

At first I did consider initializing the memory array, as suggested by Thomas, for example with a series of digests or cheap random data. But it occurred to me that this doesn't actually thwart an attacker with an excessively high rate of calculation vs memory. Since the array is predictably constructed, the attacker can simply store the current state of initialization av various stages, for example for every 100 kb of data. Then, whenever access is required to a cell that has not been modified since initialization, at most 100kb of data needs to be re-calculated.

So, the way I see it, there is no point in using anything but the fastest possible way to initialize the array as it must be assumed an attacker can get away without storing any initial values anyway.

The entire point of the algorithm is to do continual mutations and nothing else, hopefully leaving less and less room for shortcuts as the array fills up with values that forcibly must be stored. As very clearly pointed out by Thomas below, this establishes a strong correlation between the amount of memory that can be used and number of iterations.

So, given the condition that the number of iterations must be large enough to properly seed the array, does the algorithm hold up?

Let $n$ be the number of "memory cells", and $t$ the number of iterations (i.e. the three steps you describe in your question). Then we see that at each iteration, each cell has an equal probability of being picked. Then, the probability that any one cell is not selected on this iteration is:

$$1 - \frac{1}{n}$$

And hence, the probability that one cell is never selected, is:

$$\left (1 - \frac{1}{n} \right )^t$$

And so if the attacker uses an intelligent memory cell addressing system, he really only needs:

$$b \cdot n \cdot \left [ 1 - \left (1 - \frac{1}{n} \right )^t \right ] ~ ~ ~ \text{bits of memory}$$

Where $b$ is the cell's size. For $b = 256$, $n = 128 ~ \text{MB} / b = 4 \cdot 10^6$ and $t = 200000$, we get:

$$\text{Memory required} \approx 6.25 ~ \text{MB}$$

Far less than the $128 ~ \text{MB}$ expected. And that's a lot of iterations. For $t = 2 \cdot 10^6$, we need $50 ~ \text{MB}$.

Now look at the probability of a cell only getting used once (then saving its value is irrelevant), and watch your scheme crumble. At least, if I understand it properly. To be specific, your logic fails at this point:

  Intuitively, it seems to me that any algorithm that wishes to find the
  digest after the last iteration of the above loop needs to invest in
  at least enough storage to hold all cells that have been modified.

In which you didn't consider that with your current key stretching algorithm, most cells won't be modified more than once unless you have a ludicrous number of rounds, so you don't need to invest memory to save those cells (since they are zero-initialized). Take a look at how scrypt does it - you can choose to not use any memory at all if you want, but you'll need to spend a lot more computational power. It's a trade-off. In your scheme, there is no trade-off. I can choose to not spend memory... for free.

In other words, your algorithm is a bit too simple. What you are missing is a step that initializes all the memory cells with pseudorandom (not random-access) values derived from the key, in which case storing them would be a necessity, and the scheme would a priori not be subject to this weakness.

Of course, this is all for fun and academic interest. If you need a memory-hard KDF, use scrypt.


Smallest possible certificate for IoT device I'm developing an IoT system that uses small nodes connected through RF. This allows messages under 250 bytes long. You can check it at https://github.com/gmag11/EnigmaIOT.
All messages are encrypted using ChaCha20+Poly with a dynamic key obtained using DiffieHellman algorithm. But first association is only protected with a shared key so anyone that have that key may join the network.
I'd like to use mutual certificate authentication between nodes and gateway while keeping the number of messages during association as small as possible.
What is the minimum, secure enough, certificate that you can build? How could I generate it using OpenSSL?
There is a prior question similar to this but I guess my case is less constrained. Certificate validation on an IoT device using few bytes
Maybe here there is another solution
Thank you

What is the minimum, secure enough, certificate that you can build? How could I generate it using OpenSSL?

Generally you'd need to flatten certificates if you want to go below 256 bytes. X.509 version 3 certificates have a certain overhead due to the ASN.1 tree structure. So those are not as efficient as they could be.
For smart card systems generally so called "card verifiable" certificates are used. CVCertificates are proprietary structures that are generally also specified using ASN.1. However, they try and use a minimum of bytes, generally a SEQUENCE of OCTET STRINGs with possibly a few INTEGER's and OID's thrown into the mix. They would also use flattened public keys and signatures where a minimum of overhead is used.
For instance, if Elliptic Curves are used (ECDSA) there could be a dedicated named curve used, or a single byte indication of the curve used. Then the (compressed) public key would just be a single OCTET STRING containing just X for compressed or X and Y for uncompressed as statically sized unsigned integers. Similarly the signature would not be DER encoded but consist of simply a concatenation of R and S.
Generally you'd avoid RSA. RSA can be used in such a way that part of the signature actually contains the data of the certificate itself. For this "digital signature schemes giving message recovery" are used. These schemes are however rather uncommon. More importantly, a 2048 bit RSA key only allows about 88 bits of security (compared to a AES key, for instance), and already takes 256 bytes for the signature, with the public key taking another 256 bytes for just the modulus. So generally a 64 byte ECC signatures and 33 / 65 byte public keys are preferred (e.g. P-256 or ed25519 offering about 128 bits of security).
OpenSSL command line won't support CVCertificates. Generally CVCertificates are build for a specific purpose. The OpenSSL library can of course be used for both the ASN.1 / DER functionality and the cryptographic functionality. The Java / Bouncy Castle library has some CVCertificate functionality build in that is probably just compatible with the ePassport specifications (where it is used to gain access to the biometrics on the smart card chip - or at least it could be used for that).
Currently EJBCA (an open source Java EE Certifcate Authority) offers CVCertificate support compatible with the ePassport standards. Beware that the software is relatively tricky to use and setup. As it is Open Source you could probably tweak the certificate format for it to meet your needs. But whatever you do, you are entering a rather specialized territory (... welcome!)


Digital signatures with one-way function, can messages be longer than the signature? Ethereum and Bitcoin both use 512 bit signatures, can the message that is being signed be longer than 512 bit?

Yes.

Signature length is generally unrelated to the length of the message and the length of the key.  Some signature schemes have very short signatures and long public keys, like CFS; some have short keys and very long signatures, like SPHINCS; some are more balanced in size, like Ed25519 or RSA-2048-FDH.  Only exotic signature schemes for very special purposes are limited to short messages—the vast majority are designed to handle messages of arbitrary length.

Pretty much every signature scheme is designed with a random function from messages to elements of some mathematical structure for the public-key cryptosystem.  This serves to destroy any relations in structured messages.  If we didn't do that, e.g. if we used RSA with the stupid verification equation $s^3 \equiv m \pmod n$ for a signature $s$ on a message $m$ under public key $n$, then you could trivially forge the signature $s = 1$ on the message $m = 1$ under any modulus $n$ because $1^3 \equiv 1 \pmod n$.  Instead, serious practitioners use a sensible verification equation like $s^3 \equiv H(m) \pmod n$ where $H$ is a random function from messages to $\mathbb Z/n\mathbb Z$ so you have no hope of finding an $m$ such that $H(m) = 1$.

Practical signature schemes are usually instantiated with a fixed hash function $H$ accepting arbitrary bit strings as inputs, like SHAKE256.  This is not simply ‘hashing a message, and then signing a hash’—the hash is an integral part of the signature scheme itself, not something you do in addition to signing; the security of the signature scheme relies critically on the hash.

In the signature scheme that Bitcoin uses with the OP_CHECKSIG operation, the message, a transaction, is an arbitrary bit string, mapped with SHA-256d (that is, two iterations of SHA-256, $m \mapsto \operatorname{SHA-256}(\operatorname{SHA-256}(m))$) into a scalar modulo the order of the curve secp256k1.


In RSA, given $n=100$ and $e=13$ ,Encrypt and Decrypt the plain Text "SECRET" Is this question valid as $n=100$ is not a product of two primes, but can be expressed as $100=2^2 5^2$, if valid is there any criteria for choosing $d$  and other values?

At least, there's an issue with using $n=100$ as the public modulus in RSA: that number is not squarefree. This implies that $m\mapsto m^e\bmod n$ can't be a bijection of the range $[0,n)$. And thus we must restrict the plaintext space to something lesser than $[0,n)$ if we want a deterministic decryption procedure.

Proof: if $n$ is not squarefree, there exists $s>1$ with $s^2$ dividing $n$. Let $m$ be an element of the subset $\mathcal S$ of $[0,n)$ with multiples of $s$. For $e>2$, $m^e$ is a multiple of $s^2$, which divides $n$. Therefore $s^2$ divides $m^e\bmod n$. Therefore $m^e\bmod n$ belongs to the subset $\mathcal T$ of $[0,n)$ with multiples of $s^2$. $|\mathcal S|=n/s$ and $|\mathcal T|=n/s^2$. Thus $|\mathcal S|>|\mathcal T|$. Therefore the function $f:\mathcal S\to\mathcal T, m\mapsto m^e\bmod n$ is bound to collide. Such collision is also a collision for RSA encryption on $[0,n)$.

For example, with $n=100$ and $e=13$, $m_A=65$ and $m_U=85$ both encipher to $25$. This means we can't even reversibly encipher the uppercase ASCII alphabet. If we try to use $c\mapsto c^d\bmod n$ for $d=e^{-1}\bmod\varphi(n)$ as a decryption function, it will sometime fail. For example, $m_R=82$ enciphers to $c=32$ and deciphers to $32\ne m_R$.


Pencil & paper encryption, some thoughts on polyalphabetic techniques I have an idea for a simple cipher that builds on old techniques that I thought I would share with this group.  It has probably been done but I have not been able to find a reference to it.
Given two individuals who wish to encrypt their correspondence, brevity and a one time pad is pretty bullet proof.  However there are weaknesses that can be exploited. Using a key word that can be deduced as well as common letter pairings, complexity and mistakes in the ciphering or deciphering and finally the pad or letter grid itself.
My idea is to remove as many of these failings as possible and make a quick and easy process.  Starting with the letter grid or square.  Blocks of jumbled alphabets have been used, paragraphs from books but what ever the the source the letters must be put into a table format, at least 2 copies, that are correct.  Unless one just uses a book cipher then you just need two identical books.  I do crossword puzzles and realized every day there is a solution to yesterday's puzzle in the paper.  A ready made pad accurate across the distribution of the paper.  All that is needed is the index line and column.  There are holes in the puzzle, black zones, and those could reveal the structure of the pad given enough encrypted words.  But could those be embraced.  That took me the actual enciphering technique.  Instead of complex routines what if I just use a frame.  Knowing that I need an E, I pick one in the grid and then use a piece of paper to find the two index letters, one for the column one for the row.
To summarize,
Look in the paper on a specific day and retrieve the crossword solution.
Clear text, "buy in my name"
Find a letter b in the grid or table
Put the corner of the piece of paper on the grid so that it points diagonally to the b
Follow the paper edges to the two indexes and read the characters that identify the square with b in
it.  Repeat.  Spaces could be indexed to blacked out squares.
To decipher,
Get the crossword solution for the proper date and time
Put the index row and column in place
Use a piece of paper to read the clear text from the grid
There are obvious problems, beyond my general unfamiliarity with the process, but my question would be a historic pointer to this process if there is one.  Opinion on the security of the process, breaking the cipher.  And finally given the process how many times could one use that grid?  Obviously the New York Times crossword would be a far better source than a kids crossword .. but.

What you seem to be describing is similar to a single-letter book cipher, but using the solution to a crossword puzzle instead of a book as the reference source.
While this might have some merits as an ad hoc hand cipher — after all, book ciphers have also been successfully used as such in the past — it also shares most of the drawbacks of book ciphers.  In particular:

It has no secret key, other than the choice of which crossword puzzles to use.  Anyone who can guess that, and has access to those puzzles, can decrypt the messages.  This is a violation of Kerckhoff's principle.

It cannot encrypt letters that don't occur in the reference crossword.  No Q or Z in today's puzzle?  I guess you'd better not use those letters in your message.

Its security is strongly dependent on the encryptor's skill at choosing letters uniformly at random from the reference source — something that people tend to be bad at, especially if they're tired or in a hurry or just feeling lazy.  In particular, if the encryptor keeps reusing the same coordinates for repeated letters, or tends to choose nearby coordinates for successive plaintext letters that happen to occur close to each other in the puzzle (e.g. in the same word!), or even just generally favors a particular corner of the puzzle, the security of the scheme may be substantially weakened.

Some of those problems could be remedied; for example, superencrypting the ciphertext with a simple substitution cipher with a secret key (or, perhaps more simply, just using the secret key to somehow scramble the row and column labels) could make this scheme significantly harder to crack.  But other weaknesses, like the reliance on operator diligence, are harder to patch.


Does encrypting different versions of the same file or folder with the same key make it easier for hackers to attempt the decoding? Assuming the hacker has access to the ciphers of each of the versions, will it help him/her to decipher the original file(s) by doing some sort of comparison of the ciphers?

For modern ciphers when well-implemented, no: encrypting different versions of the same plaintext(s) with the same key does not make the cipher attackable.

That's because adversaries having access to nearly the same data encrypted multiple times is part of what's assumed in the baseline attack model for all modern ciphers: Choosen Plaintext Attack. The cipher is nearly never the weak link in the security chain. That's true including for AES-CTR.

Problems do occur when the random generator used for the Initialization Vector fails, or is omitted; indeed CTR mode is sensitive to that.

To a lesser degree, some side-channel attacks could be facilitated by multiple slightly different plaintexts.


Hill Cipher with unequal matrix How can we encrypt a text in Hill Cipher with a key matrix that is 3x3 when the plaintext is even like "ATTACKS"? Do we need to add padding like "x" or "z" to make the matrix equal? Thanks.

To make the plaintext matrices equal, you could use padding with a null character, such as using "X". For example with "ATTACKS", you would get the following vectors:

$$
\begin{bmatrix}A\\T\\T\end{bmatrix}\ \begin{bmatrix}A\\C\\K\end{bmatrix}\
\begin{bmatrix}S\\X\\X\end{bmatrix}\
$$


Hash "Preimage by product" resistance Let H() be a hash function that achieves collision resistance

as well as first and second preimage resistance.

Let's equip the output set of H of a multiplicative group structure, more precisely a cyclic group.

The question

My question is: Is it hard, given $a$ to find $(b,c)$ such that $H(b) \times H(c) = H(a)$ ?

Heuristic / Intuition

Before trying a reduction to one of the hash properties, I tried to realize this function myself:

Given $a$, I take a random $b$, then I'm looking for $c$ satisfying:
$H(c) = H(a) \times H(b)^{-1}$.

Then preimage resistance of H prevent me from finding $c$.

Then my intuition is that my target function is as hard as preimage resistance, but I cannot end up

with a reduction: given $H(a)$ and an Oracle that solve my problem, I don't find a way to obtain $a$.

Identically, given such an Oracle I cannot find a way to create a collision.

Collision and preimage resistance does not imply this; suppose we select a collision and preimage resistant function $H$ with a known value $I$ with $H(I) = 1$ (the group identity); this additional assertion does not contradict the assumptions of collision or preimage resistance. Then, given $a$, we can easily output the tuple $(I, a)$; as we have $H(I) \times H(a) = H(a)$.

In addition, we can see that this problem is strictly easier than preimage or second preimage problems.  Suppose that $H$ is a random Oracle, and that the group size is $n$; then, we can solve the problem by selecting $\sqrt{n}$ values of $b$, $c$, and computing two lists consisting of the values $H(b)$ and $H(a)^{-1} \times H(c)$ and looking for a value that occurs in both of the lists, that is entry $i$ of the list $H(b_i)$ is the same as entry $j$ of the list $H(a)^{-1} \times H(c_j)$.  If the random Oracle is acts randomly, then with good probability we find a common value; this gives us a pair $(b_i,c_j)$ in $\sqrt{n}$ time; this is faster than we can solve either the preimage or second preimage problem against a random Oracle (which takes $O(n)$ time).  If we had a reduction that took fewer than $O(\sqrt{n})$ calls to this problem, this would imply that we could solve the preimage problem faster than $O(n)$, which we know we can't do.

[Note: I updated this paragraph since the answer was accepted]

As for whether this problem is easier than the collision resistance problem (assuming we don't know a magic $I$ with $H(I)=1$), neither problem can be reduced to the other, as one can devise hash functions where one problem is difficult, and the other is easy.

For a hash function for which collision is hard and "preimage by product" is easy, take an RSA modulus $N$ (of secret factorization) and a value $g$ of order $lcm(p-1, q-1)$, and define the hash function $H(x) = g^x \bmod N$ for positive values of $x$ (and asking for $H(0)$ is not allowed; 0 is not positive).  Finding two distinct values $x, y$ with $H(x) = H(y)$ is equivalent to factoring $N$, and so that's difficult; however given any $a>1$, we can find the pair $a-1, 1$ with $H(a-1) \times H(1) = H(a)$.

For a hash function for which collision is easy and "preimage by product" is hard, take a random Oracle, and define $H(x) = Oracle(trunc(x))$, where $trunc$ strips off the lsbit of $x$.  Then, finding collisions is easy (just output two values that differ only in the lsbit), however solving the "preimage by product" for H is equivalent to solving it for the random Oracle.

My intuition says for realistic hash functions, these problems are likely to be approximately equally difficult; certainly, the generic attacks against collision resistance (forming a list, rho-based approaches) can be adapted to work against your problem.


Are there any authoritative definitions of "key stretching"? This is mostly a terminology question, but I suppose that it is best asked and answered here. After browsing the Internet I have come across a fair number of completely different definitions of the term "key stretching" and would like to know if there is any consensus in the research literature about how the term is to be used, or, perhaps, that it should be avoided exactly because there is no consensus.

Some of the meanings:

Key stretching is the method of applying a KDF or PRF to some input, as to produce output of arbitrary length. Some uses RFC 5931, gnu.org. The same feature is called key expansion in e.g. RFC 5869.
Stretching the entropy of the input by increasing the complexity of the derivation process. Found this on Wikipedia and in this paper by the reputable authors Bruce Schneier, David Wagner et.al. However, it seems these authors intended this feature should be used in particular when there is a need for the first feature (key expansion).
Increase the length of the input, e.g. by concatenating it with a public salt, before applying the KDF to it. Both this feature and the second is allegedly sometimes called Key Strengthening.

Are there any better terms that are more likely to be understood correctly without having to repeat the definition each time they are used? Key Expansion for the first, Key Hardening for the second, and Salting for the third?

On the other hand, the term key expansion seems to also often be used to describe the feature of cipher algorithm key schedules, when the input key is expanded into the round keys. It would be better to have a term that distinguishes between the output of a KDF and the intermediary output of a key schedule.

In my practice (Smart Cards, often using DES and increasingly AES)

Key Expansion is often used to designate production of subkeys in a block cipher. This process is often a mere bit extraction, as part of the algorithm's Key Schedule.
Key Diversification is, almost exclusively, the process of producing a device key from its serial number (or other identifier) and a master key. This transformation must be such that compromise of the key of some devices does not compromise the master key, or the key of other devices.
Key Derivation is a general term for producing a key from another key. It is often used for Key Diversification, or the process of expanding one key to several keys of different function (e.g. a confidentiality key for CBC encryption, and an integrity key for CBC-MAC), or the process of obtaining a session key from a long-term key. The term Key Derivation tends to imply that the derived key does not leak from the original key (as illustrated in Key Diversification).

Further, I would understand Key Strengthening or Key Hardening (exclusively), or Key Stretching (less specifically) as a purposely compute-intensive transformation of a key, effectively increasing its resistance to brute force search by a parameterizable factor, e.g. in PBKDF2 or Scrypt. Key Stretching is attested in this meaning, as stated in the question. But I have also seen Key Stretching used for the process of obtaining several keys from a single one, without intend to slowdown a brute force search.

And I would understand Key Salting as the ages-old process of adding (public or mildly secret) salt to a key (of low-entropy such as a password), so that at least identical keys do not degenerate into identical cryptograms, without indication of the deliberate introduction of a compute-intensive transformation as in Key Strengthening.

I am not an authority, English is my second language, and I have somewhat changed my mind on the usual meaning of Key Stretching.


question about RSA sign/verify scheme could you please explain what is the problem here?:

I'm trying to simulate sign/verify scenario with RSA keys. For simplicity I use 64bits keys:

PK = {BE1EE24B5ACD9DE5, 10001}
SK = {BE1EE24B5ACD9DE5, 15D231A2C5B605C1}

and do the calculations using http://extranet.cryptomathic.com/rsacalc/index

scenario 1 - Ok:

m = 0123456789ABCDEF

using Decrypt method (SIGN) I'm getting signature: 43437cd86b6a2cce

then using Encrypt method (VERIFY) on signature I'm getting back original message (m): 0123456789abcdef

scenario 2 - something goes wrong:

m = FEDCBA9876543210

SIGN = b3baca40fe26f5a1

VERIFY = 40bdd84d1b86942b

why VERIFY method doesn't produce original message here?

Thank you,

The RSA operation always produces an answer modulo the modulus.

Normally, we are careful to have a 'plaintext' which is smaller than the modulus, and hence the end result is the same.  After all, the fundamental identity for RSA is:

$$(M^d \bmod N)^ e \bmod N = M \bmod N$$

If $M < N$, then the right hand side simplifies to $M$

However, in this case, you have an initial input FEDCBA9876543210 which is actually larger than the modulus BE1EE24B5ACD9DE5.  When you do this, you end up with an end result which is FEDCBA9876543210 mod BE1EE24B5ACD9DE5 = 40BDD84D1B86942B

That answers the immediate question you asked; however as you dig further into RSA, you should be aware of the following:

When we use RSA, we (almost) never apply the RSA operation directly to the value given by the application (hash result, plaintext); instead, we apply a 'padding' operation first, to avoid potential attacks that exploit the homomorphic properties (and determinism in the case of encryption) that the raw RSA operation has
During the signature operation, we really can't call the RSA operation 'decryption' (as we're not actually decrypting something that has been previously encrypted).  Normally, it is called a 'signing' or 'signature generation'.


Can a "pattern" in a series of passwords be detected from their hashes (and maybe a single raw password)? Let's say I'm a lazy user of a system with annoyingly frequent password change policies. I may have a "good" password I used initially that is only used for this system but since I have to change it every week I'm just going to increment or decrement a number. E.g.

Week 1: 545h9yEQ8k37t!VW53d7g6263!&D4grz
Week 2: 645h9yEQ8k37t!VW53d7g6263!&D4grz
Week 3: 745h9yEQ8k37t!VW53d7g6263!&D4grz
Week 4: 845h9yEQ8k37t!VW53d7g6263!&D4grz
...

And so forth...

Suppose a hacker obtains the hashed password history (i.e. the hash of each password). Are there any statistical approaches they could use to detect the (very simple) pattern being used?

I would assume the hashing algorithm used will have a lot to do with it, as well as other factors like the use of a salt, possibly the length of the password and if maybe the attacker also has access to at least one cleartext password. So I guess another way to phrase the question would be: In what sort of circumstances would an attacker potentially be able to detect a pattern from a series of hashed passwords?

In what sort of circumstances would an attacker potentially be able to detect a pattern from a series of hashed passwords?

I think the most direct answer is: When the hashing algorithm is not cryptographically secure. The main four points of cryptographic hash function evaluation are as follows (quoting wikipedia):

it is easy to compute the hash value for any given message
it is infeasible to generate a message that has a given hash
it is infeasible to modify a message without changing the hash
it is infeasible to find two different messages with the same hash

As Gumbo pointed out, strong hash functions result in wide variation of output for narrow variations of input. This is true for nearly every hash function ever considered secure, even the now discredited MD5 and Sha-1 algorithms. With most hash algorithms, the main attack vector is a collision and a close second is a decryption. I expect in my lifetime that MD5 and Sha-1 will be broken, either through a thorough decryption effort or exhaustive lookup tables (for inputs under a certain length). Pattern detection in hashes may receive some further analysis. I expect that the capability to detect the presence of a pattern will arise, but the ability to definitively state what the pattern is will hinge on the ability to retrieve the plain text.

Consider the hash values of your provided example passwords:

Password                            Hash
545h9yEQ8k37t!VW53d7g6263!&D4grz    466f4dff9339bd8837a8fa960f41fc44
645h9yEQ8k37t!VW53d7g6263!&D4grz    16731f2026d9d600e7dbf66b46db7dde

I only see 5 characters that match up between the two hashes. If you took the comparison down to the bit level, maybe half of the remaining bits are equal. This is a reasonably high degree of difference between the output, considering the similarity of the inputs.

In other words, this is likely:

  We can say with 90% confidence that the plaintext of these hashes are a maximum of x-degree difference from each other.

This is extremely unlikely:

  Clearly, the user is following a pattern of incrementing the highest bits of their password every week.

Especially considering that all of the attacks on hash functions are actually interested in this:

  Oh, the hash is x? y, z, a, b and c plaintexts all map to that hash for this algorithm.

This is the rainbow table approach to password cracking, and it is very common. Most large security breaches that make headlines come from the store of passwords being leaked (most commonly through a web-based SQL injection attack).

Since you phrase it from the perspective of a hacker obtaining hashes of your password, let me put it to you another way. How much do you trust the security of the entity storing your hashes? Supposing that said entity is storing your previous hashes (which given the requirement to change it every week, I also find it likely that they will enforce a difference or minimum degree of difference which pretty much requires them to store a history), if they are breached such that the complete list of your previous password hashes are taken, it's not that much more unlikely the attacker can compromise the systems in an ongoing way and simply start recording password plaintexts as they come in.

There is a particular situation where you may be at risk in the way you imagine. If you are ever told that your new password is too similar to a previous password, then the authority almost certainly storing a list of information about your previous passwords which is less cryptographically secure. If this list is taken along with the hashes, then you're much more likely in danger of your pattern being found out. Read up on string metrics if you're interested in this - most of those metrics (as solutions for enforce password differences) would certainly require your password to be stored in plaintext.

Update: The previous two paragraphs are not necessarily true. It is possible to calculate similarity between old and new passwords, if the change password procedure requires you to provide the old password(s). See this security question for details.

If you suppose that one of your plaintext passwords is known by an attacker (through some other attack vector), that does change the problem by quite a lot. I feel I should emphasize again, however, that this would be really a very outlandish attack on your password - if an attacker can gain one plaintext password, it is almost certainly easier for them to repeat that attack than to use some type of extrapolation for your other passwords. Furthermore, if one of your plain text passwords is known, you had darn well better change your pattern for generating new passwords, preferably starting with new, distinct high-entropy starting point.

Almost all attacks on cryptographic hash algorithms remain theoretical. If there were to be a sudden break through in a pattern/similarity attack on hashes, it would certainly make headlines (in certain circles). If we really are talking about an attack target that justifies major research efforts here, and we suppose that a number of your password hashes are known and a plaintext version from your history is also known, the attacker would probably also need to know what hash algorithm is being used and what salts are used for the given passwords. These are things that may be difficult to discover, but do not provide any additional robustness to your security: once they are known, and an attack is feasible, you need to redo your entire security apparatus.

But, if a plaintext is known, it's far easier attack, in my opinion, to simply compute variations on the plaintext yourself. Given a plaintext password, a known algorithm and salt values, and just one other hash result, your example pattern could be detected in just n attempts (where n is the length of the password, multiplied by some small, constant factor). Such a cracking attempt would follow this procedure:

increment a character
compute the hash
not a match? next character

If you complicate the pattern, the amount of attempts required increases. For example, you have a pattern for choosing which character you increment each time, then for the attack to predict your next password, they must have at least as many hashes for the length of your pattern to repeat. This is essentially defining a search space for the number of permutations. So if the attacker accurately predicts that only one character changes by one bit in each new password, then only n * m possibilities exist. So for your example passwords with 32 character length (n) and call it a-zA-Z0-9!-+ 72 possible values, that's only 32 * 72 = 2304 possibilities to search, far, far less than the 220 possibilities in the theoretical lower bound of MD5 algorithm security.

Changing a second character to an arbitrary value (not an incremental value), squares the search space, which gets you back into the range of cryptographic security (2304^2 ~ 2^22). But if they have a history and know you're only changing one character at a time, then it's only 2304 searches for each step in the history (multiplicative, i.e. linear growth of the search space instead of exponential).

Hope that helps, even if I didn't provide the actual complexity of pattern detection in hash values (because such an attack does not yet exist for any cryptographic hash function).

Edit: I should probably provide a disclaimer. I am not a crypto expert, just a hobbyist/novice applying reasoning and analysis from what little I know.