Question regarding of the ECC test vector format I am trying to find some ECC test vector for using.
I just find some post (like this) and github resource (like this )
They are good reference to my C test code but I'd like to get some more advice...

Most of the test vector given looks like such format:

k (or m):m = 20
X = 0x83A01A9378395BAB9BCD6A0AD03CC56D56E6B19250465A94A234DC4C6B28DA9A
Y = 0x76E49B6DE2F73234AE6A5EB9D612B75C9F2202BB6923F54FF8240AAA86F640B8

which by my understanding, k (or m) is the private key and (X，Y) are the public key--so (X,Y)=(m dot G), G is the base point defined by NIST or BP curve as “standard”.
Q1：Is such understanding correct?

It is meaningful to see the X/Y are both 32Byte for curve sepc256k1--so expect the key length would be 256b(32byte);

my question is about the privite key (denote as m or k).
for some test vector, m(or k) is given as:

m = AA5E28D6A97A2479A65527F7290311A3624D4CC0FA1578598EE3C2613BF99522

some other test vector m(or k), however, would be like below:

k = 112233445566778899
k = 10
k = 57896044618658097711785492504343953926418782139537452191302581570759080747168

These are all pure number, so
Q2: Does that mean we need convert them to hex--and by doing that I can get exactly 32byte test vector?

so (X,Y)=(m dot G), G is the base point defined by NIST or BP curve as “standard”. Q1: Is such understanding correct?

Yes, that sounds likely to be right.

  Q2: Does that mean we need convert them to hex--and by doing that I can get exactly 32byte test vector?

What format your C test code handles is, well, up to your C test code.  What they represent is an integer, however you choose to store it, in the scalar ring of the curve.

  and some other curve like BP-521, does that mean the key bit lenth is 521b?

What BP-521 refers to, I don't know, but if it's anything like E-521 or NIST P-521, it likely refers to the size in bits of the coordinate field modulus, i.e. the field in which the coordinates $x$ and $y$ live in: the Mersenne prime $2^{521} - 1$ is convenient as a modulus for arithmetic because $2^{521} x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod{2^{521} - 1}$, so a reduction step only takes a shift-and-add.

Hasse's theorem implies that the size $\ell$ of the scalar ring and the size $q$ of the coordinate field can't be much different, $|\ell - (q + 1)| \leq 2\sqrt q$, so the scalar ring modulus $\ell$ is also going to be near $q = 2^{521} - 1$ in this case but may be off by about $2^{261}$.


PGP String-to-Key specifiers I've been reading through the PGP Standard and here I'm a little confused. This section is discussing converting string data to a session key. I'm confused about the paragraph in bold. First off, what does it mean by "hash context"? Secondly, which "data" is it referring to? Is that paragraph still talking about what to do if the hash is too small?

  Simple S2K

  This directly hashes the string to produce the key data.  See below
  for how this hashing is done.

   Octet 0:        0x00
   Octet 1:        hash algorithm

  Simple S2K hashes the passphrase to produce the session key.  The
  manner in which this is done depends on the size of the session key
  (which will depend on the cipher used) and the size of the hash
  algorithm's output.

  If the hash size is greater than the session key    size, the
  high-order (leftmost) octets of the hash are used as the    key.

  If the hash size is less than the key size, multiple instances of
  the    hash context are created -- enough to produce the required key
  data.    These instances are preloaded with 0, 1, 2, ... octets of
  zeros (that    is to say, the first instance has no preloading, the
  second gets    preloaded with 1 octet of zero, the third is preloaded
  with two    octets of zeros, and so forth).

  As the data is hashed, it is given independently to each hash
  context.  Since the contexts have been initialized differently, they
  will each produce different hash output.  Once the passphrase is
  hashed, the output data from the multiple hashes is concatenated,
  first hash leftmost, to produce the key data, with any excess octets
  on the right discarded.

Yes, it's still talking about the case where multiple hashes are needed to get to the key size. Such a function is called a key expand function.

It explains that they are taken independently (different contexts) over the passphrase (the data). A different context means that the calls to the hash functions don't interact; $H$ is seen as a single call to a complete hash function.

For example, with a 160-bit hash (e.g. SHA-1) and a 256-bit key, you would concatenate $H(p)||H(0x00||p)$, then take the leftmost 256 bits (i.e. discard the rightmost 8 octets).

If you needed a third hash block, that would be $H(0x00||0x00||p)$, etc.


CBC-MAC based on PRF Why is the block cipher in the CBC-MAC taken to be a pseudo random permutation (PRP) and not a pseudo random function (PRF)? We don't need the bijective property of the PRP. So why go with it?

The CBC-MAC construction indeed can use a PRF instead of PRP. It is now based on PRP due to historical reasons: the blockciphers used for CBC-MAC were based on permutations.

From the security point of view there will be no difference: the security proof for the CBC-MAC first converts PRP to PRF (which is indistinguishable up to $2^{n/2}$ queries) and then derives an actual upper bound on the adversary's advantage.


How much (home PC) CPU time is required to generate a prime number of a given size? How much CPU time is required on a typical home computer to generate a prime number of size 100 bit, 200 bit , 512 bit and 1024 bit using given random bits of the respective sizes?

Please note that the prime number computed should be immediately next to the given random number, e.g. if the random number is 15, the computed prime number should be 17.

I want to know approximate time range on a typical home computer for the above mentioned prime sizes.

By the prime number theorem, the average (asymptotic) distance from a prime $p$ to the next prime is $\log p $. So, on average, one must test $\log p$ integers for primality before finding the next prime. However, $\log p$ grows very, very slowly: even for 1024-bit numbers, $\log p \approx 710$.

Primality testing is well-understood, and very fast algorithms exist. For example, per AKS primality test, there exists a deterministic primality test with runtime $\tilde{O}(\log^6 p)$. Since we would have to run this test for (on average) $\log p$ integers, the runtime ends up becoming $\tilde{O}(\log^7 p)$. That's if you want an asymptotically-fast, deterministic test; in practice something like Miller-Rabin will do better, with a runtime of $\tilde{O}(k\cdot\log^3 p)$.

I guess the answer is "not much CPU time at all," but how much exactly depends on the CPU, memory speed, algorithm chosen, system load/usage, ... etc. All of those messy details are abstracted away with the use of Big-O notation (as above), so I think that's a more useful viewpoint.


How is it possible for a VPN connection to be created through the ISP? I will be theoretical here. Let's say you want to create a VPN connection with some VPN provider. You have to agree on some key to encrypt the data. how can you get the key without your ISP knowing it? Even if you are the one who creates the key, the ISP still sees it as it's being sent to the VPN provider.

An analogy would be, say...
Alice(you, or the client), John(ISP), and Bob(VPN provider) are sitting in a room.
Alice is trying to convey a message to Bob without John understanding it.
So Alice tells Bob that they will speak French(instead of English). Now john knows their language. no accomplishment. Even if Alice talked about a complex method of encrypting the message, John will know it, since he is in the room.

Unless Alice and Bob had agreed on a method before they were in the room, they won't be able to communicate privately.

An other way would be for Alice and Bob to already have some keyword X which only they know, which counts as 'a method before they were in the room', but I think that's unlikely in a VPN.

End of analogy...

So how is it possible for you and VPN provider to communicatea key without ISP knowing it?

So how is it possible for you and VPN provider to communicate a key
  without ISP knowing [that you are communicating]?

You can't. The ISP will always see that there is some traffic going on. Whether the ISP will be able to see with whom you are (actually) talking depends on whether you use things like TOR and on the details of the target network, but in general the packet metadata will tell the ISP where to send the packet and thus with whom you are talking.

  So how is it possible for you and VPN provider to communicate a key
  without ISP knowing [the key used to encrypt the data]?

This is due to the "magic" of asymmetric cryptography. In short, this allows you to reduce the requirement from a trusted, secret channel (to transport a symmetric key) down to an authentic channel, ie a channel where nobody gets to alter, drop or insert malicious messages***. And as you may have guessed, in current TLS versions (1.2 and earlier**), if you use a so-called "ciphersuite" without DH, DHE, ECDHE or ECDH in the name, you are essentially encrypting a secret with the server's public key, sending it and then you both go from there and derive a key* for the session.

*: To get some neat extra security properties.
**: TLS 1.3 has explicitely removed this type of ciphersuite because of something called forward secrecy.
***: So-called certificates are then used to reduce this requirement even further from "always need authentic channel" to "sometimes need authentic channel + need to trust a third party"


Find private key from knowing random exponents are an arithmetic series Let $p$ be a large prime and $g$ a primitive root modulo $p$, and $h$ a collision-resistant hash function.

Person A chooses a random integer $1 < u< p$ and $y \equiv g^u \pmod p$ is publicly known.

The ElGamal signature scheme using exponent $k$ for a message $m$ is an ordered pair $(r,s)$ satisfying:

$r \equiv g^k \pmod p$

$h(m) \equiv ur + ks \pmod {p-1}$

Suppose now that person A chooses the exponents for the signature scheme to increase by two for every message she sends. For example if she sends messages $m_1, m_2, m_3$ then she uses exponents $k, k+2, k+4$ respectively.

Suppose that she sends a finite number of messages and such has a finite number of exponents, and that she makes her initial choice of $k$ so that all the following keys are coprime to $p-1$.

If we know that she does this, how might we be able to deduce $u$ if we intercept two consecutive signed messages?

If the messages are $m_1, m_2$ then we have signatures $(r_1,s_2),(r_2,s_2)$ such that:

$h(m_1) \equiv ur_1 + ks_1 \pmod{p-1}$

$h(m_2) \equiv ur_2 + (k+2)s_2 \pmod {p-1}$

$\Rightarrow s_1h(m_2) - s_2h(m_1) \equiv u(s_1r_2 - s_2r_1) + 2s_2s_1 \pmod {p-1}$

This is where I get stuck because I'm not sure what I can do here that is really that helpful. We don't know if $s_1r_2 - s_2r_1$ is coprime to $p-1$ so we can't immediately get $u$, but is it true that it would be coprime? If so how could you prove it? What concerns me the most is that this doesn't really seem to use the fact that the exponents used differ by $2$.

Any help would be greatly appreciated, thank you!

We don't know if $s_1r_2−s_2r_1$ is coprime to $p−1$ so we can't immediately get $u$, but is it true that it would be coprime?

I don't believe coprimality is guarranteed, however we don't need it.

If they're not coprime, it means that there are multiple solutions to the linear equations we have; however:

The number of solutions are likely to be small; bounded by $\text{gcm}( s_1r_2−s_2r_1, p-1)$
We can list all those solutions efficiently

So, what we do is go through the list of possible $u, k$ solutions, plug each one into the $r_1 = g^k \pmod p$ relation, and see which one satisfies it; our work is done.


Linear AES : expression of K in AES(P) = AP+K I am currently trying to attack a modified AES with an identity S-box. I found this topic which explains that we have the equation $AES(P) = AP + K$, with $A$ a 128x128 matrix that is not key-dependent and can easily be computed, and $K$ a key-dependent constant. However, I fail to understand where this $K$ comes from exactly. Also, would knowing its value and its expression be enough to retrieve the master key ?

This question is taken from an old Capture the Flag competition, but I believe that there is strong didactic value in presenting a full answer. However, I'm still quite new to SE, so if anyone wishes to edit or delete this answer to make it more appropriate, I promise to accept this without complaint or resentment. Regardless of whether they agree with me or not I hope that all members of the community will assume good intent on the part of other members.
I'm going to do everything bitwise (i.e. over $GF(2)$ as you have specified that $A$ be a $128\times 128$ matrix. It is possible to rework this over $GF(256)$ in the usual AES basis by treating $8\times 8$ matrices as elements of $GF(256)$. I'll build things up to make things fit neatly into the formatting, but you should find expansion easy enough. Throughout, $O$ denotes an all zeroes matrix (of appropriate size). I've not checked any of these calculation numerically and there may be errors of endianness.
Some 8-by-8 matrices
We write $I$ for the 8-by-8 identity matrix over $GF(2)$ and
$$X=\left(\matrix{0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\1&0&0&0&1&0&0&0\\ 1&0&0&0&0&1&0&0\\0&0&0&0&0&0&1&0\\1&0&0&0&0&0&0&1\\1&0&0&0&0&0&0&0 }\right)$$
note that if we have an 8-long column vector representing an element of $GF(256)$ in the polynomial basis $x^8+x^4+x^3+x+1$ with the top entry being the coefficient of $x^7$ then multiplying by $X$ is the same as multiplying by $x$ in the field $GF(256)$.
Some 32-by-32 matrices
We build larger matrices from our $8\times8$ matrices. Let
$$C=\left(\matrix{X&X+I&I&I\\I&X&X+I&I\\I&I&X&X+I\\X+I&I&I&X\\}\right)$$
which is a 4\by4 matrix of 8-by-8 sub matrices making a 32-by-32 matrix. Multiplication of a 32-long column vector by $C$ is equivalent to the action of AES column mixing on a single column. We also write
$$\sigma_0=\left(\matrix{I&0&0&0\\0&0&0&0\\0&0&0&0\\0&0&0&0\\}\right)$$
$$\sigma_1=\left(\matrix{0&0&0&0\\0&I&0&0\\0&0&0&0\\0&0&0&0\\}\right)$$
$$\sigma_2=\left(\matrix{0&0&0&0\\0&0&0&0\\0&0&I&0\\0&0&0&0\\}\right)$$
$$\sigma_3=\left(\matrix{0&0&0&0\\0&0&0&0\\0&0&0&0\\0&0&0&I\\}\right).$$
Some 128-by-128 matrices
We write
$$S=\left(\matrix{\sigma_0&\sigma_1&\sigma_2&\sigma_3\\\sigma_3&\sigma_0&\sigma_1&\sigma_2\\\sigma_2&\sigma_3&\sigma_0&\sigma_1\\\sigma_1&\sigma_2&\sigma_3&\sigma_0\\}\right)$$
note that multiplying a 128-long vector by $S$ corresponds to the AES shift rows operation. We also write
$$M=\left(\matrix{C&0&0&0\\0&C&0&0\\0&0&C&0\\0&0&0&C\\}\right)$$
and note that multiplying a 128-long vector by $M$ corresponds to the AES mix columns operation. We also write $R=MS$.
For your purely linear AES, a round of encryption consists of multiplying by $R$ and adding round key apart from the last round which consists only of multiplying by $S$ and adding round key (there is also a pre-add of key before any rounds. Thus for AES-128 which has 10 rounds
$$A=SR^9$$
for AES-192
$$A=SR^{11}$$
and for AES-256
$$A=SR^{13}.$$
If we write $k_0,\ldots k_{10}$ for the AES-128 rounds keys written as 128-long vectors, we have
$$K=k_{10}+Sk_9+SRk_8+SR^2k_7+SR^3k_6+SR^4k_5+\cdots+SR^9k_0$$
likewise for AES-192
$$K=k_{12}+Sk_{11}+SRk_{10}+SR^2k_9+SR^3k_8+SR^4k_7+\cdots+SR^{11}k_0$$
and AES-256
$$K=k_{14}+Sk_{13}+SRk_{12}+SR^2k_{11}+SR^3k_{10}+SR^4k_9+\cdots+SR^{13}k_0.$$
Expressions for round keys in regular AES
Knowledge of $K$ is sufficient to recover any plaintext from its corresponding ciphertext and vice-versa. However, it might also be of interest to recover the actual master key. In the case of 192-bit and 256-bit variants, this will not be possible as the are only $2^{128}$ possible values of $K$ and so each value of $K$ almost certainly corresponds to multiple master keys.
In the 128-bit case it is possible that master keys uniquely correspond to $K$-values. To investigate this, we delve deeper into the key schedule. The key schedule itself in standard AES makes use of the $S$-box. This means that the round keys themselves are non-linear functions of the master key. Although the non-linear function for each round key is a bijection, there is no guarantee that the linear combination of them to make $K$ is bijective and in all probability it is not. In any event, the non-linearity makes recovery of the master key from $K$ considerably more onerous than we would like.
Linear round keys
On the other hand, if we assume that our linear AES also eschews the $S$-box in the key schedule, we can recover the master key. We introduce another 32-by-32 matrix
$$T=\left(\matrix{0&I&0&0\\ 0&0&I&0\\ 0&0&0&I\\ I&0&0&0}\right)$$
whose action on a 32-bit word written as a column vector is to rotate the bytes of the word left. We also introduce the 128-by-128 matrix
$$U=\left(\matrix{I&0&0&T\\ I&I&0&T\\ I&I&I&T\\ I&I&I&I+T\\}\right).$$
With this notation if we write $k$ for the master key we have $k_0=k$ and
$$k_{i+1}=Uk_i+r_i$$
where $r_i$ is the 128-long vector which is zero apart from the last 16-bits which take the values 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36 for $i=1,\ldots,10$. Thus in this case
$$K= (U^{10}+SU^9+SRU^8+SR^2U^7+\cdots+SR^9)k+(r_{10}+Sr_9+SRr_8+SR^2r_7+SR^8r_1)$$
writing
$$V=U^{10}+SU^9+SRU^8+SR^2U^7+\cdots+SR^9$$
and
$$r=r_{10}+Sr_9+SRr_8+SR^2r_7+SR^8r_1$$
we then have
$$k=V^{-1}(K+r).$$


Can I use ChaCha20-Poly1305 as my KDF? I have two devices that use a PSK. One is embedded and extremely resource confined. I'm already using ChaCha20-Poly1305 so it would be "free" to reuse this. There is no transport encryption layer, all clear and has middlemen.
I want to establish a randomvalue/salt/kdf-base and send this to the other device on authentication so that I'm never actually using my PSK directly. Both sides know the PSK, and use this modifier to alter their stored key, and use a common derivative for packets going forward.
My plan was to use some KDF to modify my key into a temporary session key.
Is it satisfactory to use my existing AEAD like this:
nonce: the generated salt
payload: empty
additional data: empty (OR a flag of key type I want, NIST 800-108)
key: my 16Byte PSK
tag: The 16Bytes I will use as this session's temporary key

What I FEEL like this is doing is giving me a tag that will be crypto secure to prevent leakage of my real PSK, and the salt will be OK to use here as well as send over the wire so the other side can do the same thing and evaluate the auth packets going forward.
Is this at all legitimate?

Since you have ChaCha20 as the cipher, it shouldn't occupy too much resource to add a BLAKE2 hash function next to it.
The BLAKE2 hash function comes in 2 variants: BLAKE2b, and BLAKE2s. ChaCha20 uses 32-bit words, which is more compatible with BLAKE2s. The only major difference between the hash and the cipher are the shift/rotate amounts, and the HAIFA hash compression function mode of operation.
While @SAI_Peregrinus have a good suggestion, I find it a little bit radical, so if you prefer a conservative approach, you can implement an additional BLAKE2 hash function to be used in any hash-based KDF you prefer.
As for your original ideal, I wouldn't recommend it as the authenticator is based on universal hashing in a biased modular integer arithmetic.


setting the MGF hash to a different value other than the regular hash with openssl for PSS signatures In PKCS1's Probabilistic Signature Mode you have the Hash and the MGF Hash. Both appear to be, by default, sha1, with the OpenSSL CLI client, however, I can change it to sha256 with the following:

openssl dgst -sha256 -sigopt rsa_padding_mode:pss -sigopt rsa_pss_saltlen:-1 -out signature.txt -sign privatekey.txt plaintext.txt

What if I wanted to have the Hash be sha256 and the MGF Hash by sha1? Is that possible? I just wonder because with Java the default mode for OAEP encryption changes the hash but not the MGF hash (thus making them disjoint)

Meta: since this is about using a tool not the underlying algorithm/math AIUI should be security.SE instead. If anyone can and wants to migrate feel free.

Per 1.0.2 source, -sigopt rsa_mgf1_md:name where name is the name of a hash available to EVP_getdigestbyname -- that is, implemented and not #if'ed out by default (MD2) nor manually.

For FIPS mode if relevant, I think you can set a non-FIPS hash but then the operation using it will fail, but I don't have a FIPS build set up to test.


Calculating entropy within xkcd 936: Password Strength When I calculate entropy for the xkcd Password Strength (comic 936) I don't get nearly the amount of entropy stated in the comic.

So why doesn't the the first password "Tr0ub4dor&3" have an entropy of around 50 bits? And why doesn't the passphrase sentence "correcthorsebatterystaple" represent over 100 bits of entropy?

I don't get nearly the amount of entropy stated in the comic.

Interestingly enough the reasoning for the entropy rating are actually justified in the comic by the little boxes which each represent 1 bit of uncertainty.

This means for Tr0ub4dor&3

It's estimatated that the word itself "Troubador" comes up in dictionaries which contain about $2^{16}$ words
It adds one bit for each of o,a,o of the word to encode whether the letter was replaced or not
It adds one bit to decide whether the word was capitalized or not
It adds one bit for the ordering of the trailing numeral and special character
It adds 3 bits for the unknown numeral, approximating $10$ with $2^3$ instead of $2^4$ which is more accurate
It adds 4 bits for the unknown punctuation, ie which of the approximately 16 standard ones it is

This sums up to $16+3+1+1+3+4=28$

For correct horse battery staple the reasoning is that each of the four words is drawn from a dictionary of size $2^{11}$ which means $4\times 11=44$ bits of entropy.

In both cases it can be assumed that the attacker knows the possible choices influencing the entropy estimation and that it's actually a uniformly random decision which word / pick is done.

If you want an even more thorough explanation of this comic, I can only recommend you read the bear's answer on this over on InfoSec.SE.


Finding a pair of exponents so that $c^a \bmod N = c^b \bmod N$ I am not very familiar with RSA, so this question may appear to be stupid.

Suppose that in RSA encryption, we are given $c$ (the ciphertext) and $N$ (the semi-prime modulus), can we find a pair of exponents such that $c^a \bmod N = c^b \bmod N$?

This has nothing to do with decrypting RSA; I’m just curious whether it is possible to find a pair of exponents that can produce this result? Would this be feasible if the exponents are really large numbers (for example, 300 decimal digits or more)? If so, is there any computer algorithm that I can use to do this?

If you find such you can break RSA.

Assuming the order of c is maximal(likely if c is random ciphertext).
If we have such distinct exponents  and  they must be equal mod $\lambda(n) = lcm(p-1,q-1)$.

Let the difference between the exponents be $f=b-a$, $f=0\space mod \lambda(n)$

We pick a value e coprime with e, pick a small prime and verify.
We will then calculate $d = e^{-1} mod f$

We can then find the factorization of N using the algorithm described: https://www.di-mgt.com.au/rsa_factorize_n.html

So no, if you do not know the factorization of $n$ you can't find such an exponent pair.

Example:

N= 25777 //from link
c= 1517 //randomly chosen
a = 111 //less randomly chosen(I picked)
Possible b are: 6475,12839,19203,25567 we will pick the last one
this gives us f=25456
We try e=3 and verify indeed gcd(e,f)=1
We use extended eucleadean algorithm to find d=16689 and this is exactly the value used in the above link to factorize n.

If we pick b=19203
we get f=19092 and e=3 doesn't work so we will pick e=5
We get d=7637

we follow the algorithm linked
k=de-1 = 38184

We try several g, skipping to g=5
t=k=38184
g^t % n = 1
t=t/2 = 19092
g^t % n = 1
t=t/2 = 9546
g^t % n = 15050
and we check gcd(15050,n) = 149

We found a non trivial factor of n. Q.E.D

Edit 2: Fgrieu comments the proof above does not hold in the general case. For some N the first assumption of high order may not be sound, and for very large b-a the last algorithm may not be efficient. I do not know how to rectify these. Which means though this "proof" should still be sufficient evidence that the original problem in the question of finding such a pair a,b is indeed very hard. Yet this is not a solid reduction between that problem and factorization in the general case.


Providing forward secrecy with RSA Forward secrecy with RSA is asked here:

Is perfect-forward secrecy achieved with RSA? and fgrieu gave an answer based on creating temporary RSA keys and signing them. And, in the end, he mentions

  The scheme is inefficient because the generation of a new RSA key pair is relatively expensive (and normally rare, thus not optimized for speed)

I will describe a two-pass mechanism; Send a message and receive, done.

As usual, we have Alice with $(pub_A,prv_A)$ public-private keys and Bob with $(pub_B,prv_B)$ public-private keys with modulus $n_A$ and $n_B$, respectively. They know the public-keys.

Let $n = \text{min}\{n_a,n_b\}$

Alice chooses a random number $x$ and $1<x< n$.
Alice encrypt this with Bob's public key $c_1 = E(x,pub_B)$ and sends to Bob.
Bob receives $c_1$ and decrypts $x= D(c_1,prv_B)$ to get $x$
Bob chooses a random number $y$ and $1<y< n$
Bob encrypt this with Alice's public key $c_2 = E(y,pub_A)$ and sends to Alice.
Alice receives $c_2$ and decrypts $y= D(c_2,prv_A)$ to get $y$
Finally, Alice and Bob use a KDF to derive the ephemeral key, $K_{ep} = KDF(x\mathbin\| y)$ .

It is clear that this doesn't provide integrity. Apart from this

Is there any security failure? If so, how can we improve it?
Is there any similar work before?

Some limitations of the proposed protocol:

It only applies when both parties have a private key, not in the common browser-connects-to-server scenario.
As noted by others, it is not true Forward Secrecy, for it does not protect from leak of both private keys.
Authentication of parties is not provided before knowledge of $K_{ep}$ is demonstrated, in a step not illustrated (easily added).
The scheme is only marginally less costly than authenticated Diffie-Hellman with long-term RSA keys, which solves 1 and 2.
The output of a participant's random generator can be scrutinized by an active adversary with a public key recognized by said participant.
Illustration: Bob or Trudy connects to Alice under his real identity. Alice (accepting Bob, and perhaps Trudy with less privileges) generates a random number using her RNG and sends it encrypted. He deciphers it, gaining insight about what Alice's RNG has output. Poor RNGs and poorly seeded CSPRNGs are legion in the history of security breaches.
And if that participant's random generator becomes predictable, that participant's ability to authenticate (per the method in 3) falls apart, and with that the confidentiality of whatever it's willing to transmit encrypted only to selected authenticated participants.
Illustration: Trudy, having learned a defect in Alice's RNG, can impersonate Bob because he can find $x$ by trial and error, rather than with Bob's private key. He can then receive and decipher whatever confidential information Alice is willing to send to Bob.
Bob has some control on $K_{ep}$.
Illustration: Bob is tricked into using rigged software that chooses $y$ iteratively so that the top 40 bits of $K_{ep} = KDF(x\mathbin\| y)$ are some secret function of the other 88 bits. Even though Bob runs that software in a firewalled VM and has audited that it sends nothing but what it is supposed to send, confidentiality is doomed.


RSA - Finding all possible encryption exponents Consider the standard RSA-algorithm: We have chosen two primes $p$ and $q $ such that $n:=p \cdot q$ and computed $\varphi(n)$. We now need to choose the public key $e$ such that

$$1<e<\varphi(n) \text{ and } gcd(e,\varphi(n)) = 1$$

If I am not mistaken there should be $\varphi(\varphi(n))-1$ many possible $e$'s ; we have to add $-1$ since we want to exclude $e \ne 1$.

Is there a "clever" algorithm to find all possible $e$'s other than to apply Euclid's algorithm on all numbers below $\varphi(n)$ and checks whether they are coprime to it?

We know that $\varphi(x) \ge\sqrt{\frac{x}{2}}$. The size of $\varphi(n)$ is roughly the same of $n$, so $\varphi(\varphi(n))-1$ is still a intractably large number. This means finding all possible e's is infeasible because there are too many. No matter what algorithm you use, there is no way you can find all of them in polynomial time (in the security parameter).


Secure randomized data matching? This might be a dumb question but I will go for it.

Let's say we have a data set $D$ consisting of sensitive data, and we want to be able to match if a new piece of data $S$ already exists in $D$ ($S\stackrel{?}{\in} D$) or not, and we want to be able to know which of the entries matches $S$ in $D$.

Our approach consisted of a 1-way cryptographic hash such as SHA256. However, since the dataset is relatively small (about 4 million rows) we can easily reproduce the full dataset and in effect "decode" the original meaning of the hash.

So I was wondering if it exists and algorithm that takes two parameters

$d,b$: is a pair of some sensitive data and
$s_i$: a random salt $i$

a cryptographic algorithm $C$ and a comparator $M$ such that

$M(C(d, s_1), C(b, s_2)) = \text{true}$, if $d == b$,

and

$M(C(d, s_1), C(b, s_2)) = \text{false}$, if $d != b$

So does such an algorithm or anything similar exist?

I don't believe that it is possible given the requirements you've listed.

Let us consider an arbitrary $C, M$ that meets the requirement.  To reveal the entire database, what an attacker can do is compute $C(d,s)$ for every possible $d$ (about 4 million, as you said); then, he can use $M$ to compare that to every value you actually have - this reveals everything.

To make this a solvable problem, you need to modify some assumption somewhere.

One way to address this is to prohibit an attacker from evaluating $C$ himself; we can define $C(d) = HMAC_k(d)$ for some secret key $k$.  This is determanistic (and so $M$ is a simple bitstring compare; we're assuming that we want to publicly reveal precise matches anyways, and so that's not an issue).

Another way to address this is to prohibit an attacker from evaluating $M$ himself;. One way to do this is, for some large prime $p$ and generator of a large prime subgroup $g$, we can pick a secret exponent $k$; we'd publish $g$, $p$ and $K = g^k \bmod p$.  We'd define $C(d, s) = (K^s, g^{s+d})$; we can't check if a particular $C$ corresponds to a specific $d$ if the Diffie-Hellman problem is hard.  And, the comparison function $M( (K^s, g^{s+d}), (K^t, g^{t+b}))$ (which is the comparison of an encoded $d$ and an encoded $b$) would check if $(g^{s+d})^k \cdot K^t = (g^{t+b})^k \cdot K^s$; as $K=g^k$, this is equivalent to $g^{ks+kd} g^{kt} = g^{kt+kb}g^{ks}$ or $K^d = K^b$


Does DES support different keys that lead to the same result? While bruteforcing a ciphertext, I've found multiple keys which produce the same result.

Mode is DES with ECB and PKCS5 padding.
ciphertext is TXcmk8KwIPxTHR45zAIGJPEFYj6dsgVOGseZnMcedCOhl/Qp5a8Qig==
keys are used: {      !*}, {       +}, {       *}

The tried keys are delimited by brackets {} and white space included.

The ciphertext will be decrypted as 'Does DES had multiple key for Enc/Dec?' with these keys..

tested at http://8gwifi.org/CipherFunctions.jsp and with pyDES(https://pypi.python.org/pypi/pyDes/)

The DES operation (both encryption and decryption) ignores the lsbit of each byte of the key. That is, if you flip any of the lsbits within the key, the operation remains the same.  That's what is happening in the keys you tried: the ASCII code for space is 0x20, while the ASCII code for ! is 0x21; they differ only in the lsbit.  So, if the key has a byte with the ASCII code for a space, you could replace it with a !, and it'll still be able to decrypt.  Similarly, the ASCII code for * is 0x2a, while the ASCII code for + is 0x2b; also differs only in the lsbit.

In the original DES standard, the lsbit was supposed to be used as a parity check bit (with each byte always having odd parity).  It was supposed to be a weak error check for manually entered keys.  Nowadays, no one does this parity check, and so the lsbit gets ignored.


Why is password recovery so slow for Whirlpool hash, when compared with others? I'm just curious about why brute force takes so much longer on the Whirlpool hash than it does on the others, as you will see below:

Passcovery Suite Version 3.50 build 3653 x64
Benchmark
CPU [Intel(R) Core(TM) i3-5020U CPU @ 2.20GHz]

Type: Microsoft® Word 2007
Protection: MS Office 2007, SHA1, 256-bit AES
Password recovery rate: 427 (453)

Type: OpenOffice v1.1
Protection: OpenOffice, PBKDF2/SHA1, 128-bit Blowfish
Password recovery rate: 10,654 (10,801)

Type: Blackberry 5.x backup
Protection: BlackBerry 5.x backup, PBKDF2/AES
Password recovery rate: 2,072,277 (2,082,185)

Type: WPA Handshake
Protection: WPA-PSK, PBKDF2/SHA1 HMAC/SHA1
Password recovery rate: 1,894 (1,900)

Type: RAR 3.x
Protection: RAR 3.x, SHA1, 128-bit AES
Password recovery rate: 383 (387)

Type: ZIP/Classic
Protection: ZIP proprietary algorithm, 96-bit
Password recovery rate: 26,890,751 (27,047,441)

Type: WinZip/AES
Protection: WinZip/AES, PBKDF2/SHA1, 256-bit AES
Password recovery rate: 12,891 (14,411)

Type: TrueCrypt volume
Protection: TrueCrypt volume header, PBKDF2/SHA-512/AES
Password recovery rate: 2,459 (2,476)

Type: TrueCrypt volume
Protection: TrueCrypt volume header, PBKDF2/RIPEMD-160/AES
Password recovery rate: 617 (627)

Type: TrueCrypt volume
Protection: TrueCrypt volume header, PBKDF2/Whirlpool/AES
Password recovery rate: 295 (302)

Type: Microsoft® Word 97
Protection: MS Office 97-2000, MD5, 40-bit RC4
Password recovery rate: 1,710,477 (1,703,046)

Type: Microsoft® Word 2003
Protection: MS Office XP-2003, SHA1, 128-bit RC4
Password recovery rate: 1,604,502 (1,602,161)

Type: Adobe® PDF
Protection: PDF /R 3, MD5, 128-bit RC4/AES
Password recovery rate: 125,753 (124,652)

Type: Adobe® PDF
Protection: PDF /R 6, SHA-256/384/512, 256-bit AES
Password recovery rate: 561 (563)

CPU frequency measured: 2195 Mhz

Raw results: 427, 10654, 2072277, 1894, 383, 26890751, 12891, 2459, 617, 295, 1710477, 1604502, 125753, 561

Also, one more question:

How much faster can I recover my password (20+ characters) from knowing nothing about it (it's been years since I last used it) using a GPU instead?

how much faster can i recover my password (20+ characters) from
  knowing nothing about it (it's been years since i last used it) using
  a gpu instead?

According to this benchmark, a single Nvidia Tesla V100 (the best GPU commercially available) will hit 94kH/s on that specific mode (search for 6231 on that page) which is about 300x as fast as your CPU and of course you can just use multiple GPUs. For example on Amazon's cloud services, you can have up to 8 such GPUs per VM.

Note however, if you really used a random 20+ character password, there are at least $2^{94}$ possible passwords (if you have used 20 lower case characters only) and testing this amount of passwords is infeasible (and would require $2^{77}$ GPU-years).

  I'm just curious about why bruteforce takes so much longer on the
  whirlpool hash than it does on the others

This is hard to answer. It may be that not a significant amount of effort has been invested in optimizing the Whirlpool implementations, because it's a somewhat rarely seen hash function. It may be that the huge amounts of table-lookups that Whirlpool apparently requires slow down the operations imensely compared to the register-fitting other hash functions.


Can we exchange the permutation of a sponge construction? Part of a sponge construction (like SHA3 uses) is a fixed permutation $p$; which is clearly not one-way.

Could we, theoretically, exchange the permutation $p$ with any other permutation? What basic characteristics should such a permutation have – or would, for example, a simple LFSR already represent a valid replacement, assuming it spans the whole bit-range ($r+c$)?

The security of the sponge construction rely on two parts:

the size of the capacity.
and the strength of the permutation used in the construction.

This permutation is expected to have at least the following requirement:

provide a strong diffusion (in Keccak this is provided by $\rho$ and $\pi$).
provide confusion ($\theta$ and $\chi$).

In the case of Keccak, $\theta$ is an operation mainly columns oriented.

Which is why $\pi$ will ensure that every bits of a column is evenly spread in the slice. This prevent the creation of patterns.

$\chi$ is the main ingredient in Keccak-$f$. It is the only part that is not linear. Without it Keccak would be super weak to cryptanalysis.

propagation of a difference through $\chi$

Lastly, Keccak-$f$ provides a weak alignment (resistance to truncated differential cryptanalysis). The idea is to make sure that the differences are not constrained by a subdivision of the state (byte for AES or a group of 5 bits in the case of Keccak). However, due to the weak alignment of Keccak-f, finding the lower security bounds of the algorithm is harder.

If another permutation provide such characteristics (NORX permutation? I'll let  Richie Frame answer that part. He loves NORX). Then I guess it would be another decent choice.

I haven't studied LFSR.

TL;DR: The candidate permutation must provide strong diffusion, confusion and if possible a weak alignment.


Differential addition on Montgomery curve Point multiplication using Montgomery ladder technique over Montgomery curves only require x coordinate, which in many situation leads to faster implementation as compared to point multiplication over standard curves. However, to compute point multiplication over Montgomery curves, a differential point addition operation is required https://www.hyperelliptic.org/EFD/g1p/auto-montgom-xz.html instead of typical point addition operation on standard curves.

What does this differential point addition means and how it can be computed?

Differential point addition means that to compute $x_{P+Q}$ you need not only $x_P$ and $x_Q$, but also $x_{P-Q}$.

There are a lot of possible formulas, you can find most of them here: https://www.hyperelliptic.org/EFD/g1p/auto-montgom-xz.html


Pseudorandomness of ring learning with errors My question is in Ring Learning with Errors, let $a(x)\in \mathbb{Z}_q(x)/(X^n+1)$ where $n$  is a power of $2$, be a random polynomial, $s(x),e(x)\in \mathbb{Z}_q(x)/(X^n+1)$ are the secret and error polynomial respectively with co-efficients sampled from a discrete Gaussian distribution $D_\sigma$. Now, the decisional hardness of RLWE says that the samples $a(x)\cdot s(x) + e(x)$ are indistinguishable from a random polynomial $u(x)\in \mathbb{Z}_q(x)/(X^n+1)$.

Now, my question is whether the polynomial $a(x)\cdot s(x)$ $i.e$ the RLWE sample without error will be polynomially indistinguishable from a random string? As far as I can think, the error polynomial $e(x)$ is only used for the hardness of the problem. Does it also contribute to the polynomial indistinguishability of the samples?

The reason I am asking this question is that, recently I found a new problem LWR in these papers Banerjee et al., Alwen et al Bogdanov et al. which removes the error but introduces an error with rounding each co-efficient of $a(x)\cdot s(x)$, $\lfloor p/q(.)\rceil : \mathbb{Z}_q\rightarrow \mathbb{Z}_p$. They have gone great length to prove the computational indistinguishability of the LWR samples. The computational indistinguishability of RLWR is not proven yet. if $a(x)\cdot s(x)$ is computationally indistinguishable from a random polynomial in $\mathbb{Z}_q$ then can't we say $\lfloor p/q(a(x)\cdot s(x))\rceil$ is also computationally indistinguishable from a random polynomial in $\mathbb{Z}_p/(X^n+1)$ if $p|q$

Let $R$ be the ring $\mathbb{Z}_p[X]/(X^n+1)$, where $n$ is a power of 2.  The Ring-LWE assumption says that for any randomly chosen, fixed $s\in R$, the distribution of $$((a_1,a_1s+e_1),\ldots,(a_k,a_ks+e_k))$$ is indistinguishable from the distribution $$((a_1,u_1),\ldots,(a_k,u_k)),$$ where $a_i,u_i$ are uniformly random in $R$ and $e_i$ are chosen from some distribution with small coefficients.

Of course, if one $only$ outputs $((a_1s+e_1),\ldots,(a_ks+e_k))$ without also revealing the $a_i$, then this distribution is trivially uniformly random (assuming that $s$ is invertible in $R$, but this is a minor issue) because the $a_i$ are uniformly random.  This would be a pretty useless property.

The interesting part in Ring-LWE is that even when the $a_i$ are revealed, the distribution still looks uniform.  Basically, the small additional entropy of the $e_i$ allows one to create a new uniform-looking element with larger entropy.


Does the Server Key Exchange sign a hash or text In TLS 1.2 when using ECDHE_RSA, the ServerKeyExchange message contains a signature over the server's ECDHE public parameters. My question is: Is the signature over a hash of the parameters or over a plain text of the parameters?

The specs does not clarify:

  struct {
      select (KeyExchangeAlgorithm) {
          case dh_anon:
              ServerDHParams params;
          case dhe_dss:
          case dhe_rsa:
              ServerDHParams params;
              digitally-signed struct {
                  opaque client_random[32];
                  opaque server_random[32];
                  ServerDHParams params;
              } signed_params;
          case rsa:
          case dh_dss:
          case dh_rsa:
              struct {} ;
             /* message is omitted for rsa, dh_dss, and dh_rsa */
          /* may be extended, e.g., for ECDH -- see [TLSECC] */
      };
  } ServerKeyExchange;

  params
     The server's key exchange parameters.

  signed_params
     For non-anonymous key exchanges, a signature over the server's
     key exchange parameters.

As you see, it says on the signed_params:

  a signature over the server's key exchange parameters

Signature generation includes hashing. So there is no need to perform hashing separately. This is why the signature schemes that are used will always indicate the hash to be used - either directly or indirectly using parameters.

Without the hash the signature would be vulnerable to key-only existential forgery attacks. I don't see how that would influence the security of TLS, but TLS in general tries to use standardized primitives within the protocol

Note that TLS up to 1.2 contains rather a lot of legacy constructions that would be considered non-standard by now, TLS 1.3 tries to resolve this by using RSA-PSS and SHA-2 (in the 256, 384 and 512 bit versions) which is provably secure if RSA and SHA-2 are secure.

So yes, hashing is used, but only as part of signature generation.


Forgery attack on Poly1305 when the key and nonce reused Introduction: I've tried to find how reusing one-time key compromises itself but only found information that it breaks the encryption entirely, it is written everywhere. But since no methods to reuse or restore the key were specified I don't quite get how it can be done, even with plaintext and tag given.
Problem: we have several messages and its tags, encrypted with pure Poly1305 with the same key (generated using python's Poly1305 from chacha20poly1305, implementation code) without AES and ChaCha, as it seems from the code and according to the specification.

The inputs to Poly1305 are: A 256-bit one-time key; An
arbitrary length message

I want to reuse Poly1305 key to sign custom message and therefore forge it.
What should I do to reuse the same key without knowing it on my custom message or, if possible, find the key?
Example, you've got the following data, the same key is used 3 times (data in hex : tag in hex):
Data: e8962f8dada53f589eada744bf3f9bb298be47ebd3416a59a13a709d1bf6fb4d
Tag:  825f51bb7b0f05990f03998c63a51f08

Data: 6e05652fe6a6985c1fed6604f95b133fe7a4a9f95313a8ad15d995195528efad
Tag:  53cc694570e89ec66350b4d7877ea58a

Data: 46a683f0a164bf6e19ee0b05f4c65f1f7b1d6ec454fe0e79ec4debfb22da36c1
Tag:  cba1048b9ee15929a16f0cfe5f4547b1

In Poly1305

16-byte AES key k
16-byte additional key r
16-byte $n$ nonce

is required. The obligations of the users

Any protocol that uses Poly1305-AES must ensure unpredictability of the secret key $(k, r)$.
The sender must never use the same nonce for two different messages

The obvious attack is the crib-dragging that destroys confidentiality and this doesn't mean that the encryption key is revealed. And this is not the case.
The nonce for Poly1305 is calcualted as $nonce = \operatorname{AES}_k(n)$
$$\operatorname{Poly1305}( r, m, \operatorname{AES}_k(n))$$
The $r$ actually $\in \{ 2^{106} \}$ not a full 128-bit.
The Poly1305 authentication can be simplified as
$$(((c_1 r^q + c_2 r^{ q−1} + \cdots + c_q r^1 ) \bmod 2^{130} - 5) + \operatorname{AES}_k(n)) \bmod 2^{128}$$ where $c_i$'s are encoded message $m$, $r_i$ is the $r$ in bytes.
OPs case
if we omit the $\operatorname{AES}_k(n)$ for pure Poly1305 then the equation becomes
$$(((c_1 r^q + c_2 r^{ q−1} + \cdots + c_q r^1 ) \bmod 2^{130} - 5) \bmod 2^{128}$$
Now, for simplicity only consider a small message that has 16-bytes and the same key and nonce is used. Then the for loop inside the while loop will work only once.
void poly1305_gmpxx(unsigned char *out,
    const unsigned char *r,
    const unsigned char *s,
    const unsigned char *m,unsigned int l)
  {
    unsigned int j;
    mpz_class rbar = 0;

    for (j = 0;j < 16;++j)
        rbar += ((mpz_class) r[j]) << (8 * j);

    mpz_class h = 0;
    mpz_class p = (((mpz_class) 1) << 130) - 5

    while (l > 0) {
        mpz_class c = 0;
        for (j = 0;(j < 16) && (j < l);++j)
            c += ((mpz_class) m[j]) << (8 * j);
        c += ((mpz_class) 1) << (8 * j);
        m += j; l -= j;
        h = ((h + c) * rbar) % p;
    }
    //Omitted since Pure Poly!
    //for (j = 0;j < 16;++j)
    //    h += ((mpz_class) s[j]) << (8 * j);

    for (j = 0;j < 16;++j) {
        mpz_class c = h % 256;
        h >>= 8;
        out[j] = c.get_ui();
    }
}

then we have
mpz_class h = 0;
mpz_class c = 0;
for (j = 0; j < 16 ;++j)
    c += ((mpz_class) m[j]) << (8 * j);

h = (c * rbar) % p;

for (j = 0;j < 16;++j) {
    mpz_class c = h % 256;
    h >>= 8;
    out[j] = c.get_ui();
}

The last loop actually outputs the 16 bytes of the $h$, since $p = 2^{130}-5$ is slightly less than the modulus.
Hint: play with the message, especially the upper part.
Note: rfc8439 replaced  RFC 7539

RFC 7539, the predecessor of this document, was meant to serve as a
stable reference and an implementation guide.  It was a product of
the Crypto Forum Research Group (CFRG).  This document merges the
errata filed against RFC 7539 and adds a little text to the Security
Considerations section.


How do zero knowledge protocol with vertex-3-coloring work? I'm currently not sure if I understood how the zero knowledge protocol with vertex-3-coloring works. I'll describe what I think I've understood and I'll write my questions in bold.

Zero-knowledge-protocols in general

What are they good for? What is a typical scenario?

I think they are good for authentication (The verifier wants to authenticate the prover):

The prover sends a graph for which he knows know a three-coloring to the verifier. They have to be sure that an attacker can't change this graph before the verifier gets it.
When the verifier wants to authenticate the prover, she asks for the colors of the vertices of one edge:

The prover chooses a permutation for colors
The prover applies this permutation the his coloring
The prover sends the permutated colors of the two vertices of one edge to the verifier

The verifier repeats step 2 as often as she wants.

I've found a good interactive example where you can play this game.
This site includeas another question:

[...] but also raises the question whether or not the prover is just outright cheating

How can I be sure that the prover actually has a three-coloring?

e.g. lets assume that the prover always answers (red, blue) for any request of the verifier. What would go wrong?

(After reading this great example I think there has to be some probability-part that I currently miss)

Vertex 3-coloring

How can the prover efficiently generate a big graph with a valid three coloring? How can he make sure that it is actually difficult to get a three coloring for this graph?

Zero knowledge in general

  What are they good for? What is a typical scenario?

This is an interesting question. One application is authentication: You can choose the secret yourself and not even the server will know it, and it will never be transmitted in any way. You just prove you know the secret again and again. However, in practice this is rarely used. Another application is.... security theory. If a protocol can be shown to hold some zero knowledge property, you are sure the correct protocol execution will not reveal any information about the secrets.

Vertex 3-coloring

  How can I be sure that the prover actually has a three-coloring?

You mixed up two essential steps in your description: The color permutation is chosen and applied FIRST, and then the verifier chooses the edge. And therefore, the prover has to send the entire graph with commitments of the colors to the verifier first (or he could still be cheating).

  How can he make sure that it is actually difficult to get a three coloring for this graph?

He can make sure that it's difficult to find a coloring if the graph is huge. It's an NP problem, so it can be solved in exponential time. But if the parameter $n$ is small, then $x^n$ is still manageable.

  How can the prover efficiently generate a big graph with a valid three coloring?

You should not use the word "efficient" with this problem/proof at all. That is not possible. The main problem is that the probability of detecting cheating is $1/e$, where $e$ is the number of edges.Therefore, with $n$ rounds the probability of successful cheating is $(\frac{e-1}{e})^n$. It does go towards 0, but VERY slowly in a big graph. A common goal for error in cryptography is around $(\frac{1}{2})^{80}$, which would imply an incredibly huge amount of rounds.

About generating a 3-colored graph: Start with 1 node and then add random nodes and edges in a way, which doesn't break the 3 coloring. This should take $O(n)$ time.


Guidelines for cryptographic key generation I was wondering whether you know can point me to some general (basic) principles/guidelines one should follow for generating cryptographic keys? I have looked at NIST 800-133, but was hoping for some principles a bit more general and less technical.

Specifically I’m thinking of asymmetric key pair for use of RSA and symmetric key for use of HMAC. For example, I assume that the key should have some randomness to it.

Thank you.

As for the randomness it is simply sufficient to have a cryptographically secure PRNG to generate the HMAC key and RSA key pair. You should make sure that the PRNG is a well known algorithm and well seeded, and you should perform self tests during startup. Having a malfunctioning or incorrectly seeded PRNG is one of the most common reason for vulnerable keys.

The HMAC key simply consists of random bits. You can directly use the output of your random number generator.
The RSA key pair generator requires a random input to find the random primes of half the key size. This generator will likely use a high number of random bits.

With regards to key lengths take a look at keylength.com.

Make sure your hash algorithm used within the HMAC construction is of the same size as the key size.
It is strongly recommended to only choose 8-bit multiples for the RSA key size in order to reduce compatibility issues.

RSA-specific notes:

It is best to choose a public exponent in advance, 0x010001 (65537), the fourth prime of Fermat is a popular - and often the default - choice.
Key sizes of the form $2^x$ or possibly $2^x + 2^{x-1}$ are highly recommended (e.g. 2.048, 3.072, 4.096, 8.192, 16.384 bit keys).
There is technically no need to go for ANSI X9.31 key generation (now practically replaced by FIPS 186-4 with appendix B.3); however, if a private key must run on yet unspecified hardware (as long-term root keys should), it is prudent to use primes with $2^{(n-1)/2}<p<2^{n/2}$ where $n$ is the public modulus size (one of the requirements of these standards).
RSA private keys should contain CRT parameters so as to make it straightforward to speed up RSA private key operations.
Beware that an RSA private exponent may be smaller in size - even in bytes - compared to the modulus, this is no reason to worry (unless it is much smaller).
Beware that RSA key generation can take a long time compared to other cryptosystems, including asymmetric; and this time varies widely and without firm upper bound from one key to another. This is a classic issue for mass production of devices with internal key generation, or when defining a maximum delay for supervising software.

For optimum assurance you should use a FIPS or Common Criteria validated software and hardware component (HSM, smart card) for key generation, key storage and key usage. Beware that computer memory may not always be secure. Key generation is the easy part, correct key management is much harder.


How to implement access control for Automotive Embedded Systems using mbedTLS? I am trying to implement a security access scheme for Automotive Embedded Systems.I need to be able to generate a Random number(of my desired length), combine it with some secret data to send a Seed/Challenge, generate a Key internally using the same Seed/Challenge as one of the inputs to a function and then be able to compare the received key with the computed key. Could someone help me know whether mbedTLS /PolarSSL library has functions to support me in achieving my objectives? I am new to this topic and there are too many new terms that I do not fully understand.

Summary of my needs:

Generate a RN of desired length (N1 bytes)
Seed / Challenge: RN + secret_data1 (N2 bytes)
Generate Key: f1(Challenge,  secret_data2, fixed data bytes) -> N3 bytes
Compare Key: f2(received key, generated key) -> return SUCCESS / FAILURE

Thank you in advance.

As stated in the comments we can't / won't advise on whether PolarSSL is suitable to perform the operations required.

However, for your needs $N_1=N_2=N_3=32$ sounds like a reasonable choice, giving you a solid 256-bit security and no need to worry about truncation and the alike.

As for $f_1$, HMAC-SHA256 sounds like the obvious choice, also giving you $N_3=32$. You'd input the secret data as a key and the challenge and the fixed bytes as a message and you're good.

Finally for $f_2$, this needs to be the same choice as $f_1$ paired with a simple constant time comparison.

I can't promise anything, but all of this functionality is required for any TLS implementation right now, so if the low-level primitives are provided you can use the library.


Is the concept of provably secure hash the same as entropy smoothing hash functions? Is the concept of provably secure hash the same as entropy smoothing hash functions?

In the tutorial Sequences of Games: A Tool for Taming Complexity in Security Proofs V. Shoup shows us a proof of semantic security of a hashed ElGamal encryption.

In order to get that proof (pag. 9) he put the following condition: we need a family of keyed "hash" functions $\mathcal{H} := \{H_k\}_{k\in K}$ where each $H_k$ is a function mapping $G$ to $\{0,1\}^l$ ($l$ a positive integer and $G$ is a group) such that this family $\mathcal{H}$ is "entropy smoothing".

He tells us that "entropy smoothing" gives us some kind of guarantee that makes it hard to distinguish $(k,H_k(\delta))$ from $(k,h)$, where $k$ is a random element of $K$, $\delta$ is a random element of $G$, and $h$ is a random element of $\{0,1\}^l$.

The author said there are ways to construct entropy smoothing hash functions, but it's just a conjecture that ad-hoc hash functions own this property.

Ricky already gave the answer, but here are some additional details.

"Entropy smoothing" hash functions are randomness extractors. Extractors are functions that extract almost uniform bits from weak sources of entropy. In a way, they spread the min-entropy of the input source almost evenly over the (shorter) extracted source, hence the smoothing.

The Leftover Hash Lemma asserts that a strong randomness extractor can be constructed using a family of pairwise independent hash functions. So, if $\mathcal{H}$ in your statement were such a family, you get $(k, H_k(\delta)) \approx (k, h)$.


Is there an actually an alternative to using Diffie Hellman in TLS handshake? After looking into how TLS handshaking works it seems to inherently include the Diffie Hellman algorithm during the point where they generate a shared secret key.  However as I look into this some more I find articles such as this: https://thecybersecurityman.com/2018/04/25/https-the-tls-handshake-using-diffie-hellman-ephemeral/

  "I published a blog post several months ago illustrating a simplified step-by-step process of how https and the TLS handshake typically work. BUT! There is an alternative approach that uses a key agreement protocol called Diffie-Hellman Ephemeral (DHE). This is a process of creating a secret key in plainsight using modular arithmetic."

Looking at the blog post mentioned it seems like the client uses the servers public key to create a shared private key and sends it back.  So it looks like the burden of creating the shared key is actually on the client, and so this is different than Diffie Hellman.  Is this correct?  If so what are the pros and cons of using one or the other?

This depends on the TLS version you're using.

In TLS 1.2, keys can be exchanged via RSA, DH (Diffie-Hellman over a Finite Field), ECDH (Diffie-Hellman over an Elliptic Curve), DHE (DH but the key is discarded after use to provide forward-secrecy), ECDHE (ECDH but the key is discarded after use to provide forward secrecy), PSK (Pre-Shared keys), and SRP (Secure Remote Password protocol).

In TLS 1.3 the insecure and overly-complex methods were deprecated, leaving only DHE and ECDHE for key agreement.

Versions of TLS before 1.2 don't have any unconditionally secure cipher options, and should not be used.

Wikipedia has a nice table, though note that it shows both the key exchange/agreement method and the authentication method in one chart, so there can be multiple rows using a given key exchange/agreement method.


In SKE, can we assume without loss that the ciphers of a fixed plaintext distribute identically? Let $(KG,D,E)$ be a symmetric encryption scheme. Fix $sk\gets KG(\lambda)$ and an arbitrary plaintext $m$.
Generally speaking, $E_{sk}$ is not deterministic, so that $E_{sk}(m)$ is a random variable, which could distribute in many different ways.
Is there a way to generically transform such a scheme to a scheme in which, for any $m$ and $sk$, $E_{sk}(m)$ distributes uniformly on its support (or at least it is indistinguishable from uniform)? Is this possible without using any cryptographic assumptions which don't already follow from the existence of an IND-CCA1 secure SKE?

Is this possible without using any cryptographic assumptions which don't already follow from the existence of an IND-CCA1 secure SKE?

Yes, symmetric-key encryption implies the existence of "uniform" symmetric-key encryption. But I don't know of a particularly direct way to show it. Below is an extremely convoluted, theoretical, impractical way to do such a transformation.

If CPA-secure symmetric-key encryption schemes exist, then so do one-way functions. This is shown in Impagliazzo-Luby.

If one-way functions exist, then PRGs exist; this is the classic "HILL" result.

If PRGs exist then PRFs exist; this is the classic GGM result.

Once you have a PRF you can construct an authenticated encryption scheme based on counter mode with a MAC like Carter-Wegman. This scheme will have the property that you need, since the ciphertext is a deterministic function of the (uniform) initialization vector + key + plaintext, and no two choices of initialization vector give the same output (since the IV is included in the output). Hence the output is uniform over the support.


Shamir's Secret Sharing of modular inverse Given a secret $K \bmod q$ which is shared among entities $E_1,…,E_n$ using polynomial Shamir's Secret Sharing, how can the inverse of $k$ be shared without revealing $k$ and $k^{-1}$?

I'm assuming $q$ is prime.

Note that $k^{-1}\equiv k^{q-2}\bmod{q}$.

We can compute $k^{q-2}\bmod{q}$ via a multiparty computation protocol such as the one outlined in this paper ($\S3.1)$. Or, since $q$ is likely a public parameter, you can even do the simple square-and-multiply algorithm (for example, VIFF provides this capability).

You might also be able to compute the modular inverse via the extended euclidean algorithm implemented using general MPC techniques. The reason I say might is that the extended euclidean algorithm does have a conditional branch in it. While this is technically not a problem for MPC, it could leak information in the real world that you wouldn't want to leak.


Clear Lucifer example and explanation? I am trying to understand the Lucifer cipher and I cant find any clear understandable example of the cipher.

Can anyone please provide me with a step-by-step example of an encryption using the Lucifer cipher?
Can you describe the relation between Lucifer cipher and Feistel
Networks?
Can you please provide references and links for further reading?

Lucifer had different versions, keylengths could be 48, 64 or 128 bits. The blocklength could be 48, 32 or 128 bits.

The Feistel structure was used there for the first time. Horst Feistel was the main designer.

Alan G. Konheim has a nice description in chapter 9 of his book Computer Security and Cryptography, including diagrams, given the many examples available for DES, you should be able to follow what happens in Lucifer. Google books has the beginning of that chapter.

One of the open expositions is in a paper by Smith, later on described by Sorkin.

It looks like DES with simpler round key bit choices and mostly shifts instead of permutations, thus weaker.

You should be good to go on from here.

References:

Horst Feistel, (1973). Cryptography and Computer Privacy". Scientific American, 228(5), May 1973, pp 15–23.
Konheim, Alan G. (2007), Computer Security and Cryptography, John Wiley & Sons, p. 283, ISBN 9780470083970.
A. Sorkin, (1984). LUCIFER: a cryptographic algorithm. Cryptologia, 8(1), 22–35, 1984.


Can Alice prove that she *did not* send an unsigned message to Bob? Suppose Alice wants to send messages to Bob. However she doesn't trust Bob. She believes that Bob may publicly disclose a fake message, claiming that it came from Alice. This message will cause the public to have a negative opinion of Alice.
Alice can use signing to prove that a message came from her. However, she cannot prove to the public that the fake message did not come from her. Bob can always claim that the fake message was not signed by Alice because then Bob could publish the signature along with the message and prove to the public that the message came from Alice.
Assuming that the public trusts Bob more than Alice, how can Alice prove that the message is fake? Ideally, she should not be able to prove that the message is fake if she really did send the message to Bob in an unsigned manner.

There is no way to prove that the message is fake without some trusted authority (such as GMail's DKIM) that automatically provides some level of non-repudiation without Alice being able to influence it (Alice can't send a message with DKIM disabled if she's using GMail).
Alternatively, Alice can habitually sign every message and ensure that those who are receiving those messages know that any unsigned message is not to be trusted. This only works if her audience is technically-minded and not easily swayed by emotive language and unfounded claims. Since you say that the community trusts Bob more than Alice, this is really a no-go.
From a cryptographic point of view, there is no way to prove that a message is not authentic as long as the message and signature can be separated in any way whatsoever.


What is difference between PRG, PRF, and PRP Until what I have gotten is: A PRG is generator is a part of PRF that produces pseudo-random values for the function. PRF is semantically secure and has no worries of being invertible. Fine, then where is PRP used? What is PRP, where it comes to, how it benefits.

A Pseudo Random Function is a function that is indistinguishable from a function selected at random from the set of all functions with the same domain and value set. A Pseudo Random Permutation is, similarly, a bijective function that is indistinguishable from a bijective function selected at random from the set of all bijective functions over the same domain. For instance, a cryptographically secure block cipher parametrized by a secret key is a PRP.

The term PRG is otoh most commonly used for stateful functions that are used for generating successive pseudo random strings, e.g. to be used as a key, iv, salt, nonce etc.


Is javascript RSA signing safe? I'm currently working on a secure open source messaging system (https://github.com/DSMNET/DSMNET). I'm currently using the cryptico.js (https://github.com/wwwtyro/cryptico) library to encrypt all the messages sent.

Now to authenticate users my server will send a random string and the client will encrypt the string and sign it. The server will check if the signature matches the public key stored for the user.
Users will generate their public and private key with their password.

I would like to know if using Javascript RSA and using RSA signatures to authenticate is safe or can people forge RSA signatures.

If you implemented it well, and there is no MITM (i.e. use authenticated comm channel), then it is difficult to forge the RSA signatures (meaning you can use them safely).
However, in your implementation there are 2 other major factors that you need to consider:

One is the use of Javascript as a coding medium: there are many who consider Javascript to be a bad languange to use for writing security code due to some notable exposure to adversaries. I personally am not in that camp - if you take good care of securing your environment where you run the JS code you will be OK.
Also, there are some advantages of letting the user's browser do the work (and Java has its own set of implementation / management problems), this may be a prudent choice.

The second point is a major one: you selected “cryptico” engine, and we don't know how well the guy who wrote and modified the code behaved.
Some critical security routines there were modified by him, and this should ring a big red alarm bell over its usage. If you plan to use it for anything important, you need to pass the published code through a critical security/cryptographic review before usage.


Efficient protocol to give out N known items randomly to k>=3 parties without independent bodies There are $N$ items which are to be uniformly randomly distributed (every possibility has equal probability) to $k\geq 3$ parties, such that no individual party can change the probability of getting certain items.

Party $0\leq i<k$ would receive $N_i$ items, such that the sum of all $N_i$ is $N$.

No party would want any other party to know any more things than their own $N_i$ items.

The only form of communication possible is a broadcast to all other parties.

You can assume an upper limit on the amount of computation possible during the protocol.

Question: Is there a method to give the $N$ items to the $k$ parties such that:

The probability of any party finding out another party's information is less than any chosen positive amount.
The method terminates in finitely many steps with probability 1.

I am particularly interested in alternative solutions which requires less computation (time) on average than my answer presented below.

Consider the following protocol to find the sum of secret integers among $k$ parties:

Pairs of parties use RSA or any other communication protocol to set up a secure channel of information. In the exchange, they declare a number $x$ such that the first party subtracts $x$ from their secret integer, and the second party adds $x$ to their secret integer.

When the following is satisfied:

Each party has communicated with at least 2 parties.
The graph formed by vertices being parties and edges being communications is biconnected. It is sufficient to make a cycle graph.

If every pair of parties communicated, then any communication between any pair of parties would not get any more information than them sharing which cards they have.

The parties announce their modified numbers, and the sum can be calculated by summing the modified numbers. This step takes $O(k)$ (or $O(k^2)$ for the other version) time.

Consider the following protocol to generate random numbers:

Each party generates a random bitstring of a certain and commits to it (by salting and hashing). All parties reveal their bitstring and the xor of all the bitstring is taken to be used for random numbers. This takes $O(k|bitstring|)$ time.

The main protocol is:

Each party $i$ chooses $N_i$ random integers in the range $(0, N^2)$ and commits to them. The parties would try to find the order of their random integers (number of other random integers chosen by all the parties which are less than it). We also have to detect when two parties choose the same integer.
For each integer $x$ from $0$ to $N^2$, each party is supposed to find the number of integers they have less than $x$, summing all the secret integers would give the order of $x$. If the order of $x$ and $x+1$ differs by more than $1$, rinse and repeat. As there are $O(N^2)$ numbers, this step takes finitely many steps with probability 1. This takes $O(N^2k)$ time.
Now, each party knows the order of their random integers, and the set of orders of the random integers is from $[0, N)$. We map the orders to the $N$ items by selecting an order and using the random number protocol to to generate enough bits to select a random item from the remaining items. This step takes finitely many steps with probability 1, and is expected to take $O(N \log N)$ bits, hence taking $O(kN \log N)$ time.
To prove that a party owns the item, the party has to reveal the random integer used for that item, and since it was committed in advance, other parties can check it.

Example: With $N=k=3$, the $N$ items being $A, B, C$, $N_0=N_1=N_2=1$, parties $0, 1, 2$ select the numbers $5, 2, 7$ respectively among $(0, 9)$.

Using the secret summing method, they get the orders (which we denote as $\text{ord}$) of the integers:

$\text{ord}(0) = 0$

$\text{ord}(1) = 0$

$\text{ord}(2) = 0$

$\text{ord}(3) = 1$

$\text{ord}(4) = 1$

$\text{ord}(5) = 1$

$\text{ord}(6) = 2$

$\text{ord}(7) = 2$

$\text{ord}(8) = 3$

$\text{ord}(9) = 3$

It is easy to check that there are no two randomly selected numbers that are the same.

Using the random number generator, the parties decide that the order of $0$ maps to $C$, $1$ maps to $A$ and $2$ maps to $B$.

Hence, party $0$ gets $A$ as $1=\text{ord}(5)$ maps to it.

Party $1$ gets $C$ as $0=\text{ord}(2)$ maps to it.

Party $2$ gets $B$ as $2=\text{ord}(7)$ maps to it.


Is Diffie-Hellman post-quantum secure? If Alice and Bob have a secure channel for key exchange and Mallory doesn't man-in-the-middle attack them, but in the future eavesdrops on their connection and sees the key exchange, can Mallory break it like RSA with a quantum computer?

A quantum computer solves the discrete logarithm problem for both finite fields and elliptic curves. Being able to efficiently calculate discrete logarithms implies being able to break Diffie-Hellman, so Diffie-Hellman on either of them is not secure against an adversary who owns a large quantum computer.

There might be other groups in which DL problem is hard even against a quantum computer, but I've never heard of such a group.


How are old encrypted messages recovered for the sender? Take ProtonMail as an example. It encrypts all emails with some kind of asymmetric keys. But obviously, they can't store my private so the key must be obtained when I log in. This means, they must be able to generate the same key multiple times. I thought they used my password to deterministically generate the keys, but then I changed my password and I was still able to open my old emails. How is that possible?

Here is a way you can do it: use a key derived from the password to encrypt your long-term private key.

When you want to register an account with password $\mathit{pw}_0$:

Generate a key pair $(\mathit{sk}, \mathit{pk})$.
Generate a salt $s_0$.
Derive $k_0 = \operatorname{Argon2id}(\mathit{pw}_0, s_0)$.
Compute the ciphertext $c_0 = \operatorname{AES-GCM}_{k_0}(\mathit{sk})$.  (Set nonce = 0.)
Store $(\mathit{pk}, s_0, c_0)$.

When you want to read your mail:

Rederive $k_0 = \operatorname{Argon2id}(\mathit{pw}_0, s_0)$.
Decrypt $\mathit{sk} = \operatorname{AES-GCM}_{k_0}^{-1}(c_0)$ (or report authentication failure).
Use $\mathit{sk}$ to decrypt mail.

When you want to change your password to $\mathit{pw}_1$:

Rederive $k_0 = \operatorname{Argon2id}(\mathit{pw}_0, s_0)$.
Decrypt $\mathit{sk} = \operatorname{AES-GCM}_{k_0}^{-1}(c_0)$.
Generate a fresh salt $s_1$.
Derive $k_1 = \operatorname{Argon2id}(\mathit{pw}_1, s_1)$.
Compute the ciphertext $c_1 = \operatorname{AES-GCM}_{k_1}(\mathit{sk})$.
Replace $(\mathit{pk}, s_0, c_0)$ by $(\mathit{pk}, s_1, c_1)$ and erase all copies of $c_0$.

(This is presumably close to what ProtonMail does.)


How secure is this modified Bazeries Cylinder? This device is a modification of the Bazeries cylinder, it has two stacks of 5 rotors which each bear two alphabets plus numbers 0-9, one in correct order and one in random order ( 36 characters in each row ). Plain text in 5 letter groups is entered by setting the rotors as in Fig 3. The shaded character on the bottom rotor is read and the whole rotor stack is then turned ( keeping the individual rotors in alignment ) so that this character appears on the top rotor.  The enciphered group is then read from top to bottom as in Fig. 4.  This group is then re-enciphered by the same procedure using the lower stack of 5 rotors, producing a doubly-encrypted code message.( Figs. 5 & 6 )

Obviously this would be devilishly difficult to decipher without knowing the rotor stack sequence and the random sequences of the alphabets on each rotor.  Frequency analysis, Kasiski tests and Index of Coincidence tests do not reveal any useful information. My question is, could this coding system be broken by other than brute force methods ( which would be very tedious and expensive ) ?

To maintain security, the rotor stack sequence would be changed in accordance with a code book list ( or other protocol ) after every 50 groups.

A specimen of code produced with this device follows :

4FRLO 7W0W9 PL84F 7BITX 9VNBN H0U81 DJ3PU 1R27H 9SCN3 FJTBG 9CIQK D1ZZU
IJB4H YML6O DHTZU IFJBH UABHD L37I8 RYEXE QQ9SU BJX4G YG0KT 7GJAT X0XOW
R9DT1 MEH3A EU8HO 9J70M DO0E4 STXQS 9VS5N 9ICZ9 KN4TR 55AMC ELLGW AQ2IH
AEOC8 E0EMP FM36V OGBEP 8MLO5 0GY00 KSRQN MMJ88 DQYB8 4GU0X 1ZPVU FQTQD
4LVKW 4W4G0

How secure is this modified Bazeries Cylinder?

That depends on what you expect us to compare it to. I doubt you’re looking for an answer along the lines of “it’s more secure than Scytale, but less secure than AES”. Therefore, I will try to narrow it down a bit by saying that it is safe to assume it can not – in any way – provide the same security levels that modern cryptographic algorithms are able to provide. Some attacks are obvious; while others are merely a question of investing some time and effort to practically cryptanalyze the nitbits.

  My question is, could this coding system be broken by other than brute force methods ( which would be very tedious and expensive ) ?

Yes, it can. Mentioning only two of many examples: it definitely won’t hold for a second when applying a chosen-plaintext-attack or a known-plaintext-attack – which would both count as “valid breaks”.

Don’t get me wrong. It’s a nice design and it surely baffled some adversaries back in the days. Yet, in a (let’s just call it) “near-quantum” world, the cryptographic attractiveness  of this classical-cipher is nothing more than dust in the wind… a distant reminder of days where things like computers did not exist and security was easier to achieve and uphold.


Convert plain text as numbers to encrypt using RSA All mathematical description of encryption functions assume, despite the use of the word plaintext, that the message to be encrypted is a sequence of numbers. For example RSA with $n=pq$ assumes that one wants to encrypt a number $x$ less than $n$  than a message consisting alphabets. It says encrypted form of $x$ is $x^e\pmod m$. Is there any (open) standard for converting text to numbers before encrypting?

As ASCII values go only up to 256. Does one take plain text, say 10 characters at a time, and read it as a 10-digit number in base 256? This is my own guess. I would actually want to know the exact standard followed in the industry.

Is there any (open) standard for converting text to numbers before encrypting?

Well, yes and no.

There is the Unicode standard which converts each character as a single code point. But that's not what you are after, you want to encode a complete text into a number.

To do this the standard way to operate is to use two conversions:

convert the text to bytes using a character-encoding;
convert the bytes to a (large) number.

Now RSA certainly operates on numbers, but the RSA PKCS#1 standard is defined to take bytes as input. So step 2 is an integral part of PKCS#1 called OS2IP. OS2IP means Octet String (bytes) to (two) Integer Primitive. OS2IP simply interprets the bytes as an unsigned, big endian number.

OS2IP however happens after padding, which is performed on the input bytes. Padding is required to make RSA secure.

So that leaves us with the first step: converting the text to bytes. Text is stored inside computers as a string of characters. Character encoding is what is used to convert a set of characters (an alphabet) to bytes. The most logical character encoding is no doubt UTF-8, which encodes most of the most common Unicode characters to a single byte, ASCII compatible representation.

Unicode with UTF-8 is definitely as close as you can get to a commonly accepted standard.

If you want to experiment with raw/textbook/unpadded RSA, you could first encode using ASCII or UTF-8, and convert the resulting bytes to a number using OS2IP - but keep in mind that this is insecure.


Prove that decryption in LWE based PK cryptosystem works correctly except with negligible probability The LWE cryptosystem is defined as follows:

Key Generation:
Secret key: random vector $s \in F_q^n$.

Public key: $\{c_i\}_{i=1}^m$, where $c_i = (\textbf{a}_i, \textbf{a}_i \cdot \textbf{s} + e_i)$, where $\textbf{a}_i$ are uniformly random, and the $e_i$ are chosen according to $D_e$.

Encryption:
Message is a bit $w$. Choose random bits $b_1,\ldots,b_m$ and then the ciphertext is $\sum_{i=1}^m b_ic_i+(0,\lceil q/2 \rceil w)$.

Decryption:
To decrypt $(u,v)$, compute $v-\textbf{s}\cdot \textbf{u}$, and output $0$ if this value is closer to $0$ than it is to $\lceil q/2 \rceil$. Otherwise, output $1$.

The distribution $D_e$ is defined as follows:

$D_e$ satisfies $\sum_{i=1}^{m}e_i < q/4$ for $e_i$ chosen according to $D_e$. Here, $e_i$ are small numbers, and $q$ is some positive integer.

Now, $\textbf{v}-\textbf{s}\cdot \textbf{u} = (\sum_{i=1}^m b_ic_i + \lceil q/2 \rceil w) - (\textbf{s}\cdot \sum_{i=1}^m b_ic_i)= ...$, but then I'm stuck.

Can someone help me out?

Denote the public key as $({\bf a}_i, a'_i)_{i=1}^m,$ with each "sample" in $\mathbb{F}_q^n \times \mathbb{F}_q,$ where $a'_i = \langle {\bf a}_i, {\bf s}\rangle + e_i$ with each $e_i \leftarrow D_e$ i.i.d. (guaranteed that $\sum_{i=1}^m e_i < q/4$ with overwhelming probability).

Consider an encryption of 0 given by $\mathsf{ct} = ({\bf u}, v)$ over the private random coins $(b_i)_{i=1}^m,$ where ${\bf u} = \sum_{i=1}^m b_i{\bf a}_i \in \mathbb{F}_q^n$ and $v = \sum_{i=1}^m b_ia'_i \in \mathbb{F}_q$

(You can consider the case of an encryption of 1, by just adding $\lceil q/2\rceil$ to $v,$ of course.)

The decryption algorithm applied to $\mathsf{ct} = ({\bf u}, v)$ will output 0, correctly, so long as $v - \langle {\bf u}, {\bf s}\rangle$ is closer to 0 than $q/2$; that is, if $|v - \langle {\bf u}, {\bf s}\rangle| < q/4.$

And $$v - \langle {\bf u}, {\bf s}\rangle = \sum_{i=1}^m b_ia'_i - \langle\sum_{i=1}^m b_i{\bf a}_i, {\bf s}\rangle$$
and since $a'_i = \langle {\bf a}_i, {\bf s}\rangle + e_i,$ we get that the above is then
$$... = \sum_{i=1}^m b_i\left(\langle {\bf a}_i, {\bf s}\rangle + e_i\right) - \langle\sum_{i=1}^m b_i{\bf a}_i, {\bf s}\rangle$$
$$= \sum_{i=1}^m b_i\langle {\bf a}_i, {\bf s}\rangle + \sum_{i=1}^m b_ie_i - \langle\sum_{i=1}^m b_i{\bf a}_i, {\bf s}\rangle$$
$$= \sum_{i=1}^m b_ie_i.$$

Since we are guaranteed (except with $\mathsf{negl}(n)$ probability..) that $\sum_{i=1}^m e_i < q/4,$ we conclude that $|v - \langle {\bf u}, {\bf s}\rangle| < q/4$ implying correctness of decrypting 0-bits. The proof for 1-bits is the same -- but you'd end up with $\sum_{i=1}^m b_ie_i + \lceil q/2\rceil$ at the end, so the result would be closer to $q/2$ than 0, again by the upper bound w.h.p. on sums of $m$ small errors that you started with.


How do I compute CDH given squared-CDH? This describes a way of proving CDH <=> and Square-DH. The thing I don't get - how to efficiently compute $\operatorname{CDH}(U,V)$ from $\operatorname{CDH}(U,V)^2$. Isn't square root problem is hard in general? (In case of composite order fields for example). As far as I understand computing square root is as hard as factorization of $N$, where $|G| = N$ which can be hard in non prime order group.

So what am I missing here?

This is a matter of computing square roots in $\mathbb Z/p\mathbb Z$.

If $p \equiv 3 \pmod 4$ is prime and $a$ is a quadratic residue so that the Legendre symbol $(a|p) \equiv a^{(p - 1)/2} \pmod p$ is 0 or 1, then $4 \mid p + 1$ and $$\bigl(\pm a^{(p + 1)/4}\bigr)^2 \equiv a^{(p + 1)/2} \equiv a^{(p - 1)/2 + 1} \equiv a^{(p - 1)/2} a \equiv a \pmod p.$$  Consequently, the square roots of $a$ are $\pm a^{(p + 1)/2}$.  (If the Legendre symbol $(a|p)$ is -1, then $a$ is not a quadratic residue.)
If $p \equiv 5 \pmod 8$ is prime, then either $\pm a^{(p + 3)/8}$ or $\pm a^{(p + 3)/8} 2^{(p - 1)/4}$ are the square roots of $a$, depending on whether $a$ is a quartic residue modulo $p$ or not.  Proof left as an exercise for the reader.
If $p \equiv 1 \pmod 8$ is prime, then there's no nice closed-form expression or deterministic algorithm for computing square roots in $\mathbb Z/p\mathbb Z$, but the Tonelli–Shanks or Cipolla algorithms can do it in constant expected number of multiplications in $\mathbb Z/p\mathbb Z$.
If $p$ is not prime, then finding square roots modulo $p$ is as hard as factoring $p$.  But in discrete log systems, we usually worry about prime moduli.  Proving relations between DLOG, CDH, SDH, SQRT, and FACTOR for a composite modulus is left as an exercise for the reader.


Can S/MIME be still considered secure? Previoulsy I had asked this question at https://stackoverflow.com/questions/18235983/can-s-mime-be-still-considered-secure but I feel this forum is topic-wise the right place.

Recently there has been a discussion whether secret service agencies have access to certification authorities. Also before that several CAs were facing security problems being attacked by hackers.

Given this, I am wondering whether S/MIME can be still considered secure. Some time ago I had generated a free email certificate from one CA. To my surprise the key had not been generated with a tool on my own computer; instead it was generated by the CA and emailed to me. I am wondering:

If this CA is infiltrated by a secret service agency, will they have access to my private key and can use it to decrypt emails encrypted by my public key?
Are there tools to generate S/MIME keys on an own computer? If so, is it possible to send only public keys to a CA to get them signed?

Yes, obviously if the CA generated your private key, they might keep it and share it with anybody.
Yes on both counts.

In fact, the normal way to generate a certificate -- whether for a Web server (TLS) or for yourself (S/MIME or TLS client) -- is to create a "Certificate Signing Request" and send it to the CA. The CSR includes your public key, not your private key; the private key never leaves your own computer.

See http://www.howtoforge.com/how-to-encrypt-mails-with-ssl-certificates-s-mime for step-by-step instructions using OpenSSL. Note: That page has instructions for creating a self-signed certificate, but further down it shows how to create a CSR and then sign it with a private CA. In practice you just send the CSR to the CA and pay them to sign it.

Assuming this is how you get your signed certificate, the only thing you lose when the CA is compromised is that somebody else could pretend to be you. That does sacrifice one of the purposes of S/MIME (authentication). Such forgeries are very easy to detect after the fact, so even if our security services have this capability, they could not use it very often without getting caught.


First contact when using Public-key cryptography? Are there any "smart", useful ways when doing first contact in Public-key cryptography? Besides physical contact.

Example: SSH has the "VisualHostKey=yes" (but this also requires to know the image...)

Visual Validation of SSL Certificates in the Mozilla Browser using Hash Images
https://www.cs.cmu.edu/afs/cs/user/mjs/ftp/thesis-program/2004/tay,evelyn.pdf

You're asking for techniques to establish trust in a public key upon first connection. There are three major approaches to this problem:

Out-of-band-verification. This generally relates to methods which use methods which don't go over the current communication channel to verify a public key.

Pinning. If you use pinning, you hard-code your public key (or a hash thereof) somewehere (for example in your app) and then validate that the pin matches the public key. This is also done in browsers, for example Chrome pins the Google certificates. Also there are ways for webservers to signalise that they want their current public key pinned (HPKP).
Physical verification. In this scenario you likely want to confirm the public key associated to some physical entity so you go to that person, verify their identity and then associate the public key they claim to belong to them (in person) with them.
Other channels. In this scenario you generic "other channels" for your verification. For example if you want to exchange PGP keys, you confirm the hash of the key over Twitter or your favorite messaging app.

Certificate Authorities (CAs). This is the approach where one (or a set of) entity(-ies) certifies a public key to belong to a specific entity (eg a person). The signing keys  of the CA(s) are verified out of band (as per 1).

SSL PKI. For the web, the summary basically describes what is done.
DANE. DANE means that you put your public key (or a hash thereof) in the DNS so it can be confirmed "out-of-band" that way. This is placed under "CAs" because the DNS itself is secured by DNSSEC which has a strict CA hierarchie.

Web-of-Trust (WoT). In this scenario everybody becomes a CA basically and certifies other people's key depending on the verification they have reached out-of-band. This allows you to traverse the graph that the WoT forms and find a path from you to the new public key, maybe because two of your friends already have seen and verified said public key.

PGP WoT. The above is basically how the PGP WoT works.
Notary-like Approaches. This is a slightly different approach but is also based on the idea of "many CAs". Basically you have a set of (more or less trusted) notaries and each time you encounter a new website you ask them what public key they see. If these match what you see you have some confidence that your key is good if not, you know you're attacked.

Trust-On-First-Use. This approach is the most straightforward one. Assume the first connection is ok and keep the public key or a hash for verification against later connections. Obviously this doesn't solve your problem.


what is a rigorous definition of "proof-of-possession"? I cannot find a rigorous definition of what the "proof of possession" attribute means.  Different webpages seem to give conflicting definitions:

Some of them say that it means, literally, proving that you possess a value (a key or a password):
https://www.w3.org/2012/webcrypto/webcrypto-next-workshop/papers/webcrypto2014_submission_8.pdf
https://idm.unl.edu/4254-proof-possession
This doesn't seem like a useful definition, though, because almost every crypto operation involves a key, so by this definition, anything would constitute "proof of possession", including just giving the key out to prove you have it.

Some of them say it specifically refers to proof of possession of a private key in a public-private key pair:
https://help.sap.com/doc/saphelp_nwpi711/7.1.1/en-US/4c/a09b7e1fd9634ae10000000a421392/content.htm
http://www.convertwriteservices.com/assets/docs/API/certj_reference/javadoc/com/rsa/certj/PKIService.html
but I think this is probably wrong, as more authoritative sources like https://tools.ietf.org/html/rfc7800 talk specifically about proof of possession in the context of symmetric keys.

One page which is on an internal company wiki that I cannot share, which says that proof of possession means proving that you possess a value, without sending the value to the other party.  Ironically, this is the definition that seems most likely to be correct, since it's most consistent with how people use it, even though I can't find any public-facing webpages giving this definition.

So is it the case that definition #3 is correct and that sources which give definition #1 or #2 are (mildly) wrong?

The closest notion used in the literature seems to be “proof / argument of knowledge” (PoK / AoK). See [GMR, BG] as well as Wikipedia for its definition. Indeed, giving out the key would be a proof of knowledge (but it's not of much interest to cryptography).
The part about “not sending the value to the other party” seems to be related to zero-knowledge (ZK). ZK requires the interaction yields no extra effect beyond the prover convincing the verifier. For example, if a ZKPoK is used to prove possession of a secret key with respect to a public key, then the verifier does not learn any extra practical information about the secret key after being convinced. See [GMR] and Wikipedia.


Why does the padding in Merkle–Damgård hash functions like MD5 contain the message length? I understand the need for padding in MD5. But why do we append the message length to the padding?

I heard it strengthens the hash but how?

Please provide an example if possible and how it applies to this quote:

  The inclusion of the length-block effectively encodes all messages such
  that no encoded input is the tail end of any other encoded input.

Why a message being the tail of another message is bad (if it is)?

MD5, like other hash functions, uses the Merkle-Damgard construction. You take the message and break it up into fixed-size blocks. You start with an intialization vector (IV), which you feed into a compression function along with the first block. Take the output (it will be the same length as the IV), and feed it into the compression function along with the second message block, and so on.

Call the compression function $c$ and the "raw" (unpadded) hash function $h$, we have $$ \begin{align*} h(ZABCD) &= c(h(ZABC), D) \\&= c(c(h(ZAB), C), D) \\&= c(c(c(h(ZA), B), C), D) \\&= c(c(c(c(h(Z), A), B), C), D) \\&= c(c(c(c(c(I,Z), A), B), C), D)\end{align*}$$ with a fixed initialization vector $I$ (each letter represents a block).

Different hash functions use different compression functions. The goal is to prove that we can find a collision in the hash function only if we can find a collision in the compression function (the next step would be to argue that finding a collision in the compression function is extremely difficult).

How would this argument work? We could restate our goal as follows:

If you give me two messages that cause a collision in the hash function, I can find two pairs of inputs for the compression function that cause a collision.

Here's how I do meet this goal: I take the two messages you give me, and split them into blocks. Then I find the right-most block that the two messages don't have in common. For example, if the first message (after padding) has blocks $ZABCD$ and the second has blocks $XKCD$, then third block from the right is different ($B$ vs. $K$).

Since $h(ZABCD) = h(XKCD)$, I check to see if $h(ZABC) = h(XKC)$. If not, I have my collision:

$$ h(ZABCD) = c(h(ZABC), D) = c(h(XKC), D) = h(XKCD). $$

On the other hand, if $h(ZABC) = h(XKC)$, this isn't really a collision for $c$, since the input values are the same. So I go back a block and see if $h(ZAB) = h(XK)$, and do the same thing. If they are not equal, I have a collision: $c(h(ZAB), C) = c(h(XK), C)$. If they are equal, I go back another block.

But now that $B \neq K$, I don't need to worry about whether or not $h(ZA) = h(X)$. I know that $c(h(ZA), B) = c(h(X), K)$ (because $h(ZAB) = h(XK))$, and since $B$ and $K$ are distinct, this is a collision – different inputs, same output.

I can go through this processes for any pair of inputs that generate a hash function collision in order to find a pair of inputs that cause a compression function collision. QED, right?

But wait!
What if when I go from right-to-left, I run out of blocks before I find two that are different? Then the argument breaks. So for the argument to work, I need my padding scheme to ensure that one (padded) message is never the tail end of another.


Size of bitwise OR between vectors represented as polynomials I am using polynomials to represent bit vectors, such that the value of the d-th coefficient is $1$ if the d-th bit in the vector is $1$, and $0$ otherwise.
For example, the vector $A = [1, 1, 0, 1, 0]$ is represented by the polynomial $P_A(x) = 1 + 1x + 0x^2 + 1x^3 + 0x^4 = 1 + x + x^3$.

I understand that I can find the number of bits $1$ in the bitwise AND of two vectors, $|A \wedge B|$, by multiplying $P_A(x)$ and the "inverted" $P_B(x)$ and checking the (d-1)-th coefficient in the resulting polynomial, as explained in Scalar product of vectors over polynomial rings.

Now I want a similar way to find the number of bits $1$ in the bitwise OR: $|A \vee B|$.
Considering $|A \vee B| = |A| + |B| - |A \wedge B|$, so far I thought about of $|A|$ by multiplying $P_A(x) \cdot P_1(x)$, where $P_1(x)$ is the polynomial having the value $1$ for all coefficients. Then, I would do the same to find $|B|$.

This would require three polynomial multiplications and two additions: $P_A(x) \cdot P_1(x) + P_B(x) \cdot P_1(x) + P_A(x) \cdot P_B(x)$.
Since the first two have $P_1(x)$ in common, it is possible to simplify it a bit: $(P_A(x) + P_B(x)) \cdot P_1(x) + P_A(x) \cdot P_B(x)$, using a total of two polynomial multiplications.

My question is: Is there a way to do this using fewer polynomial multiplications?

It holds that $$\begin{align}|A \vee B|&=d-1-|\overline{A \vee B}|\\
&=d-1-|\overline A \wedge \overline B|
\end{align}$$

Define $K(x)$ as the polynomial of degree $d-1$ with all 1 coefficients. $\overline A$ can be represented as the polynomial $K(x)-A(x)$.

Thus the desired $|A \vee B|$ is obtained by subtracting from $d-1$ the coefficient for $x^{d-1}$ of the polynomial $(K(x)-A(x))\cdot(K(x)-\tilde B(x))$, where $\tilde B(x)$ is $B(x)$ with "inversion" of coefficients, that is the coefficient of degree $i$ becomes coefficient of degree $d-1-i$.

We can use polynomial addition rather than subtraction: $d-1$ minus the coefficient for $x^{d-1}$ of the polynomial $(A(x)+L(x))\cdot(\tilde B(x)+L(x))$ also works (where $L(x)$ is the polynomial of degree $d-1$ with all $-1$ coefficients).