Is it possible to implement the Signal Protocol without a server? My question is regarding the Signal Protocol[1]. Is it possible to implement the protocol securely, without a server?

(I have no particular motivation for the question other than to understand better how the Signal Protocol works, what kind of trust I give to the server, and what attacks are possible if the server can be hacked or if server <> client communication can be monitored).

Imagine a room with a big whiteboard (or a chalkboard). This is our "server", but anyone can enter the room at any time and make any modification they want. The goal is for Alice to initiate an encrypted, asynchronous conversation with Bob by writing messages on the board.

My understanding is that neither XEdDSA/VXEdDSA nor the Double Ratchet component of the protocol are affected by the board being public. Is that correct?

That leaves the other two components of the protocol.

X3DH

As stated in X3DH Section 4.7, "Server Trust"[2], the following properties are true when using a server, and would still be true using a whiteboard:

The server can cause communication to fail by refusing to deliver messages (someone can erase the board).
The server can refuse to provide pre-keys, or somebody can drain pre-keys (erase them from the board), reducing forward secrecy.

What are the other attacks which would be made possible by giving anyone access to the board?

Sesame

As stated in Sesame Section 6.3, "Protecting Server Communications"[3]:

  If an attacker is able to impersonate a victim device when authenticating to the server, the attacker could fetch messages being sent to this device. The attacker would not be able to decrypt these messages, but would learn sender UserIDs and DeviceIDs.

This would obviously be impossible to prevent on the whiteboard, so everyone would be able to see who is communicating with whom.

Sesame also relies on server <> client communication being encrypted and authenticated. From the same section:

  Communication between devices and servers should be encrypted and authenticated. This limits the amount of metadata that is exposed to eavesdroppers, and makes it harder for third-party attackers to perform active or passive attacks on device-to-device communications.

What attacks would be made possible by giving anyone access to the board?

Conclusion

As best I can tell, the only reduction in security comes from the fact that anyone would be able to monitor who is talking to whom.

Forward secrecy could also be reduced by eliminating pre-keys. Would that completely eliminate forward secrecy?

How could cryptographic deniability be affected?

Have any similar protocols ever been developed which would give the same properties as the Signal Protocol without trusting a server at all (e.g. you could literally do it on our whiteboard)?

Thanks, and I hope you have fun thinking about it!

[1] https://www.signal.org/docs/

[2] https://www.signal.org/docs/specifications/x3dh/#server-trust

[3] https://www.signal.org/docs/specifications/sesame/#protecting-server-communications

Expanding from the whiteboard example as that is just a transparent central server.

This is not an issue although with a different model, you just need to decide which properties you care about.

Without a trusted entity maintaining the lookup of verified phone numbers to public keys, you will need to rely on another means. I recommend using the public key directly to effectively null out this layer while keeping it orthogonal such that lookups may exist in the future.
Without a trusted store-and-forward service you'll need to establish a rendezvous point such a DHT or wrap another chat protocol that knows nothing about Signal. Wrapping another protocol can solve (1) opportunistically, although the service (like Signal) may return keys it controls and is just as trusted and centralized.
If you do not have a store-and-forward service then the signed prekeys are redundant. This does not reduce forward secrecy, but it does require the 3DH handshake to occur before messages may be sent. So no 0-RTT semi-forward-secure messages.
If delivery is synchronous and ordered you can simplify double-ratchet.
You may use an anonymity network such as Tor to hide who is talking with whom. Each user could be their own ed25519.onion service. But if they are, then double-ratchet and 3DH are both redundant and we've got ricochet.im.

Social graphs and deniability depend on the above choices. I.e. ricochet.im hides the social graph great using onion routing; if you want better, you'll need a mixnet. Or if you forward messages over some existing service, they can see the social graph prove you communicate and record the ciphertexts forever to verify any revealed keys and plaintexts.

On another note: you might want to take a look at matrix.org's libolm, a double-ratchet implementation that does not assume server cooperation.


Why didn't people redesign the key scheduling algorithm of DES to use longer keys instead of using 3-DES? To overcome short key length of DES, Triple DES was devised. What would go wrong or why didn't people redesign the key scheduling algorithm to use longer keys?

Same as the reason of why not switching to AES (or any other 80+ key bits algorithms available at the time).

Because we want to reuse whatever "hardware" (chip design) resources available to do the blockcipher calculation, and re-designing the key schedule would prevent us from doing so since the existing hardware cannot compute the new key schedule.


RSA Signature Weak Padding Attack Assume that we have a message $m$ of size $n$, and it is padded with two 01 bytes in front. Then  the signature $s$ is computed using a private key $ks$. Can we still use the Known Message Attack to create a signature for message $m^2$ or $pad||m||pad||m$ by multiplying the signature with itself? Or will the padding stop this despite being weak?

If we note $|m|$ the number of bits in the bytestring coding the message $m$, the first padding considered is $m\mapsto \tilde m=257\cdot2^{|m|}+m$, and the signature is $m\mapsto\tilde S(m)=S(\tilde m)=\tilde m^d\bmod N$, where $S$ is the textbook/naked RSA signing $m\mapsto m^d\bmod N$. Notice that for any $m$ small enough that $m^2$ can be signed, we can derive $S(m^2)$ as $\big(S(m)\big)^2\bmod N$; and if $n^2$ is too big, we may still have $S(m^2\bmod N)=\big(S(m)\big)^2\bmod N$.

NO, we can not derive $\tilde S(m^2)$ as $\big(\tilde S(m)\big)^2\bmod N$. That equality holds if and only if $\tilde m^2\equiv\widetilde{m^2}\pmod N$. At least, when $m$ is small enough that $\widetilde{m^2}<N$ or some similar huge bound (not explicit in the statement), that simplifies to $\tilde m^2=\widetilde{m^2}$, and there is no $m$ matching that: notice that the square of an integer which two leftmost bytes after removing leading zeroes are 0101 has its two leftmost bytes after removing leading zeroes among {0102, 0103, 0104}. I conjecture, without proof, that above said bound, we can not efficiently come up with any solution without knowing the factorization of $N$.

But NO, the scheme is not secure. Even with the (unstated) constraint of messages of the same width, it is easy to come up with distinct messages $m_0, m_1, m_2, m_3$ such that $\widetilde{m_0}\cdot\widetilde{m_1}=\widetilde{m_2}\cdot\widetilde{m_3}$; and then we can derive $\tilde S(m_3)$ as $\Big(\tilde S(m_0)\cdot\tilde S(m_1)\cdot\big(\tilde S(m_2)\big)^{-1}\Big)\bmod N$, where the inverse is computed $\pmod N$.

More generally, linear padding schemes (such as the second one proposed) are weak in RSA, and subject to attacks. See Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem, section 4.1.

Even non-linear padding schemes may be quite weak; for example (INCITS/)ISO/IEC 9796:1991 (informally known as ISO/IEC 9796-1, and mostly described in section 11.35 of the HAC) was trounced in 1999, then withdrawn.

Using a padding scheme with a hash helps, but is not an insurance of security against such forgeries, even in combination with a linear padding scheme; for example ISO/IEC 9796-2:1997 was shown to have a vulnerability (not practically exploitable in any setup that I know of), even in its strengthened variant of 2002, now officialy designated as ISO/IEC 9796-2 scheme 1 and in wide use, that prescribes a hash of at least 160 bits. However I do not know of any attack (even theoretical) on the padding of RSASSA-PKCS1-v1_5 of PKCS#1.

Conclusion: when at all possible, and in any setup where an adversary could obtain the signature of chosen messages, use RSA signature schemes with provably secure padding based on Full Domain Hash, like RSASSA-PSS of PKCS#1, or when message recovery is needed ISO/IEC 9796-2 schemes 2 or 3 (although I have never seen a complete formal proof of the later ISO/IEC 9796-2 schemes, I trust them enough).


Is it safe to use cipher block sizing instead of padding? I'm using this kind of technique instead of padding of cipher buffer (here goes pseudo-code):

struct {
   int size;         //size of cipher buffer
   byte[32] vector; //random IV (block size is 256 bits)
   byte[] buffer;    //encrypted buffer
}

Cipher data encrypted using block cipher with CBC chaining using IV specified as vector

I'm storing this structure "as-is" and in order to decrypt it decrypting buffer block by block then just cutting buffer to size.

Question is: is it safe/secure? Any hints/criticizm?

Yes, this is fine.

There is a practical disadvantage in space used, if you don't otherwise need to store the size in plaintext. A size field will usually take 32 or 64 bits, whereas typical padding adds one byte on average. Also, if you use encrypt-then-MAC you need to include the length as part of the authenticated data.


Does knowledge of original file size provide a cryptographic weakness? I'm encrypting files using an AES-256 CBC cipher and an SHA-256 HMAC every 64KB in the file. Since AES CBC needs an amount of input bytes to be divisible by 16, I use PKCS#7 padding to bring the amount of bytes up to a count divisible by 16 at the end of the file.

For this and for most cases of cryptography, does knowledge of the original file size expose a weakness enabling an attacker to gain an advantage in decrypting the data? If someone had knowledge of the way an encryption system works, it may be feasible for them to guess the original file size. Is this a problem?

Yes, feasibility to guess the plain text size might be a serious vulnerability in real life scenarios. For instance, in traffic analysis the approximate length of the messages in a communication, might reveal enough information about what is communicated, for it to be possible to deduce the gist of it. If such threats exist in your case, however, you will probably have to consider more radical counter measures than just apply a few byes of PKCS#7 padding at the end of your file fragments.


I think PBKDF2 may be better than Scrypt? Looking for someone to point out my logical error People seem to mostly recommend scrypt these days, but I'm not sure if this should be the case? I'll structure this post by just making an argument for PBKDF2 over Scrypt and then you can reply telling me where I'm wrong.

Okay, let's say I'm Google and want to hash my user's passwords in the most secure way possible. Currently some of the most recommended ways are PBKDF2 (with SHA512 for example) and scrypt.

I want each password to take around 1 second to hash.

I look into PBKDF2 and see that the most efficient way to calculate hashes for it are using an ASIC.

I then look at Scrypt and see that the most efficient way to calculate hashes for it are through a balanced combination of CPU, RAM, and GPU.

Since I'm a webserver, I mostly just need CPU. I don't really need a GPU at all, only some RAM, but yeah, mostly CPU. Unfortunately, I can't even use that much CPU because I need it for serving all my concurrent requests. As a result my hashing will be weaker unless I purchase additional hardware.

In the case of PBKDF2, you will need to buy an ASIC to be ideal, and with Scrypt you will need to buy a GPU, RAM, and have a really strong CPU (yikes recent Intel security issues) to be ideal.

Is there a difference is between having X input rounds with PBKDF2 with ideal hardware (ASIC) vs having Y input rounds with Scrypt with ideal hardware (Proper balance of CPU, RAM, and GPU)? Assuming both operations take 1 second with the given input parameters, at that point aren't you mostly just guessing which will be harder in the future?

Also, it looks like either way you'll need to spend money on additional hardware.

Okay, now for my additional arguments in favor of PBKDF2:

It's been around longer and is thus more time-tested and scrutinized
It's NIST and FIPS compliant
There is more native support for it (For example, node crypto has PBKDF2 and not scrypt)

Also, an insane amount of financial incentive has lead to the development of specialized hardware for grinding PBKDF2 hashes because of the cryptocurrency phenomena. As a result, I'd imagine that not only is SHA extremely secure, but that ASICs are near the asymptote for potential performance.

Comparably, Scrypt may yet have specialized hardware developed that will allow for much more efficient computation in the future.

Lastly, is it not the case that Scrypt databases can be cracked by a botnet? Since the ideal hardware for the Scrypt hashing algorithm is pretty close to consumer hardware (CPU, GPU, RAM), is there not a risk that an Scrypt database could be be parallelized across the Botnet? For example, it is currently a concern of some cryptocurrencies that use Scrypt-adjacent algorithms that a botnet may be able to someday near a 51% attack.

Thoughts?

There's no point in using either an ASIC or a GPU to calculate a single password hash.  That's true whether you use PBKDF2 or scrypt or Argon2 or whatever.

What massively parallel devices like GPUs or ASICs are good for is hashing millions or billions of passwords at the same time.  That's useful if you're mining a cryptocurrency or trying to crack a hash for which you don't know the password, but not if you're just trying to test a single user-entered password to see if if it matches the account's password hash or not.  For that, it's much easier and more efficient to just calculate the hash on the CPU.

Basically, what parallel devices like GPUs and ASICs do is give an edge to the attackers, who have billions of passwords to test and don't really care about latency (i.e. the time it takes for a single password to get hashed) as long as the throughput (i.e. the average number of passwords hashed per second) is good.  That's why modern password hashing schemes like scrypt or Argon2 are designed to make GPU/ASIC hashing as hard as possible, so that the edge they give to attackers over legitimate authenticators is minimized.

(And yes, a botnet of compromised personal computers could indeed be used to crack scrypt hashes.   However, especially if most of those computers had half-decent graphics cards, they'd be even better at cracking PBKDF2.)


Is it secure to use ECDSA for any arbitrary point on the Elliptic Curve as the Generator point? My question concerns the elliptic curve $E$ over a prime field $\mathbb F_p$. To the best of my understanding, ECDSA requires a Generator point $G$ of prime order $n$, and the $r$ and $s$ values of the signature must be within the range $[1,n-1]$. The concept of ECDSA is to show a person that one is in possession of a secret $k$ s.t. $kG = K$, without (obviously) revealing $k$.

However, suppose that you are aware of public key $K$ and are looking to do a tweak of $K$. Let $t$ be the tweaking factor, and so $tK = K'$. If you then wanted to prove that you are in possession of $t$, how would you do that?

An immediate thought (which I am confident will not work) is to use ECDSA with $K$ as the generator point. However, it might be the case that $K$ is of a very small order $n$ which may not be prime.

If someone can shed light on how to prove that one is in possession of secret $t$, I would be very happy. Also, the verifying party is in possession of both $k, K$, the secret key and public key pair.

However, suppose that you are aware of public key $K$ and are looking to do a tweak of $K$. Let $t$ be the tweaking factor, and so $tK=K'$. If you then wanted to prove that you are in possession of $t$, how would you do that?

The obvious way to do this is a Schnorr proof of knowledge, which does precisely what you're looking for; given a public $K, tK$, it demonstrates that you know $t$.  Wikipedia lists the interactive version; it can be made noninteractive by having the prover generate $c$ based on a hash of the commitment $t$ (and possibly other stuff if you need to bind the proof to something).

  An immediate thought (which I am confident will not work) is to use ECDSA with $K$ as the generator point. However, it might be the case that $K$ is of a very small order $n$ which may not be prime.

That would also work (which isn't that surprising; ECDSA is essentially based on Schnorr, tweaked enough to avoid patents that have since expired); it's kludgier, however it might be preferable if you just happen to have an ECDSA implementation just lying around.  If $K$ does have small factors, you might need to work around it (as some values might not be invertable), however that wouldn't appear to be a major issue.

And, if $K$ is a very small order, then deriving $t$ would be easy, no matter what proof-of-knowledge method you use (and so there's little point in the problem).  In any case, we almost always use elliptic curves where the order of the curve is $hq$, where $h$ is a small value (the most common values are 1 and 8), and $q$ is a large prime - except for a handful of points (actually, a total of $h$ points), all points have a large order (at least $q$).


Given partial key exposure and encryption oracle, can we recover full AES key? Suppose I have an encryption oracle for AES with some key $k$ (16 bytes) and that I know $n$ bytes of it. Is it possible to recover the rest ($16 - n$) in complexity less than $256^{16-n}$?

No, there is no known easier attack than doing a brute force search on the unknown key bits.

In particular, if there were, then this show an attack on the standard (no key bits leaked) AES, because what an attacker could do is go through all possible $2^{8n}$ settings of those key bits, assume those, and run his 'less-than-brute-force' attack on the remaining key bits.  If this attack (when his guess for the 'known' key bits is correct) takes an expected time of less than the time taken to compute $2^{128 - 8n-1}$ AES evaluations, then the total time will take less than the time taken to do $2^{128-1}$ evaluations, that is, it shows that there is a faster-than-generic attack


Blowfish: hex digits of pi used for s-boxes? Preface: here is the official site for the Blowfish algorithm:

http://www.schneier.com/blowfish.html

The Blowfish algorithm uses an s-box, which consists of hex digits of pi (found here: http://www.schneier.com/code/constants.txt). I'm guessing that this s-box serves a very similar purpose to the s-box in AES (right?)

However, at the bottom of that file, there is a smaller box called p_array or parray or something. I have no idea what it does! Also, is there some sort of significance to why the hex digits for pi are used, and not some random values?

Yes.  Blowfish's S-boxes serve a similar purpose as AES's S-box.

The P-array is used as part of the key schedule, to make sure that each round is different (this helps prevents slide attacks and related-key attacks).

I recommend you read the official specification of Blowfish and Wikipedia's article on Blowfish for more about the design rationale for Blowfish.

The use of digits of pi is a "nothing up my sleeve" number.

Bruce Schneier (the algorithm designer) wanted to use a random number.  For Blowfish, it basically doesn't matter what number you use, if it is random.  However, Bruce also wanted everyone to be able to see that he didn't somehow pick some very special choice of number that introduces a trapdoor.  The digits of pi are basically random-looking, and cannot be controlled by Bruce.  Therefore, they make a standard choice for a "nothing up my sleeve" number.

See also How to choose constants in a cryptographic function? and Wikipedia on nothing up my sleeve numbers.


How can one generate pairs/triplets/.../n-ary MD5 collisions Is there a way to generate n strings with the same MD5 hash?

MD5 is a Merkle–Damgård hash, so it's vulnerable to the length extension attack.

That means there's a simple way to find multicollisions using any algorithm that can find collisions for an arbitrary IV:

Find some collision $\operatorname{MD5}(a) = \operatorname{MD5}(b)$ using the normal IV.
Find another collision $\operatorname{MD5}'(c) = \operatorname{MD5}'(d)$ using the output from the first step as IV.
Combine them to valid messages that look like $a||c$, $a||d$, $b||c$ and $b||d$, except for the padding. This may require adding one more (equal) message block to get a valid padding and length.


Strict Avalanche Criterion (SAC) I would like to know the step by step method to construct the SAC dependence matrix for AES S-Box. Can someone help me?

This is a condensed explanation, but should be enough to get you to the result.

First you must generate the intermediate data.

For each boolean function and bitmask, you run through a loop, $i$ from 0 to 255:

testval = sbox(i) XOR sbox(i XOR mask)
bitval = testval AND 1
results(mask,0) += bitval

The bitval is the low bit of the test result on the s-box input $i$. The results is the sum of all the bitvals for the given mask and boolean function, in this case boolean function 0.

For the other boolean functions, you must rightshift the test value, as you are testing the other bits rather than the low bit:

divisor = 2^booleanfunction
testval = sbox(i) XOR sbox(i XOR mask)
bitval = (testval / divisor) AND 1
results(mask,booleanfunction) += bitval

The loop for the single bit mask are from 0 to 7, as that is how many there are for an s-box with 8 input bits, the mask is $2^{loop}$. The loop for the boolean function is from 0 to 7, as that is how many there are for an s-box with 8 output bits. Here is an optimized loop to calculate the results

m = 0 to 7      [loop for masks]
i = 0 to 255    [s-box input entries]
n = 0 to 7      [boolean functions]

for m:
  mask = 2^m
  for i:
    testval = sbox(i) XOR sbox(i XOR mask)
    for n:
      divisor = 2^n
      bitval = (testval / divisor) AND 1
      results(m,n) += bitval

Now that you have the results calculated, you simply display them as a matrix:

             boolean function
       7   6   5   4   3   2   1   0
   0  128 116 124 116 144 116 132 132
   1  136 128 116 124 128 144 124 120
m  2  128 136 128 144 120 128 132 132
a  3  140 128 136 128 116 120 136 136
s  4  136 140 128 128 132 116 128 116
k  5  136 136 140 120 120 132 132 116
   6  124 136 136 120 132 120 136 136
   7  132 124 136 124 136 132 144 132

This is for SAC with a single bit mask (1st order SAC) for other orders, the bitmask calculation is different, and there will be more masks, 2nd order has 28 masks for example.


Is length extension attack considered as collision? I came across a few articles about length extension attacks on cryptographic hash functions. I was very surprised to read that SHA-256 and SHA-512 are prone to length extension attacks. This seems contradictory to the fact that—to the best of my knowledge—there are no known collisions on these algorithms.

According to the comparison of SHA functions table from Wikipedia the capacity
against length extension attacks is 0 for both SHA-256 and SHA-512 which should mean that this attack does not require much computing resources.

Aren't length extension attacks considered as collisions as well?

No, the length extension attack/property is not considered a collision. It does not allow to build a collision.

The length extension property is that given the hash of a bitstring $M$ of given length $l$ (but arbitrary and unknown content), it is possible to compute the hash of $M\mathbin\|F(l)\mathbin\|E$ with $F(l)$ a short bitstring deduced from the length of $l$, and any known bitstring $E$.

It follows that if messages $M$ and $M'$ of the same length collide (have the same hash even though $M\ne M'$), then $M\mathbin\|F(l)\mathbin\|E$ and $M'\mathbin\|F(l)\mathbin\|E$ also collide. Therefore, the length extension property eases building more collisions from an existing collision among messages of the same length.

MD5, SHA-1, SHA-256, SHA-512 have the length extension property (and correspondingly, it is used to extend MD5 and SHA-1 collisions). SHA-3 and SHA-512/256 do not have the length extension property, because enough of the internal state does not make it to the output. The situation is not clear cut for other SHA-2 hashes truncated to more than half their internal state size (e.g. SHA-224 has only 32 bits of resistance to length extension).


Can deterministic ECDSA be protected against fault attacks? In a paper by Barenghi and Pelosi, it was described that fault attacks could be used to derive the secret key when using deterministic ECDSA as described in RFC6979 by @Thomas_Pornin

  Deterministic (EC)DSA. The purpose of the attacker in this case is to recover the value of the secret key $d$, from the values of the correct signature $(r, s)$ and the erroneous one $(\tilde r, \tilde s)$. The attacker is able to build the following simultaneous equation set on $\mathbb{Z}^*_q$ in the unknowns $d$ and $k$:

  $$ \left\{ \begin{align} s &\equiv_q (\texttt{H}(\texttt{msg})+d \cdot r) \cdot k^{-1} \\ \tilde s &\equiv_q (\texttt{H}(\texttt{msg})+d \cdot \tilde r) \cdot k^{-1} \end{align} \right. $$

  and solve it for

  $$ \left\{ \begin{align} d &\equiv_q \textstyle \frac{(s - \tilde s) \cdot \texttt{H}(\texttt{msg})}{r \cdot \tilde s - \tilde r \cdot s} \\ k &\equiv_q s^{-1} \cdot (\texttt{H}(\texttt{msg})+d \cdot r) \end{align} \right. $$

  The amount of computation required to derive the secret key is negligible, and it is possible, in case an unreliable fault injection technique is being used, to confirm whether the correct values of $d$ and $k$ have been extracted deriving the deterministic $k$ corresponding to the $d$ via the procedure specified in [9], and checking it against the one obtained from the simultaneous equations.

Can deterministic ECDSA be protected against such fault attacks?

As already said by fgrieu in his answer, this is possible.

There are multiple ways to protect deterministic ECDSA against fault attacks, but these ways will depend on your fault model.

If you consider only a single fault model, then any construct requiring the attacker to perform two faults to achieve his goal will be an acceptable countermeasure... On the other side if you consider the attacker is ubiquitous and can perform faults of her choosing at any point in time at any location of the chip, then you most likely won't find any way to counter her. It is a common assumption, backed by practical experiment that performing two localized faults on the same computation is hard, even more so if the value of the fault is important.

So, how could you deal with single faults in deterministic ECDSA?

Well you could do as fgrieu says and do the verification process, but then a second fault in the very last step could simply trigger the verification to output "true" instead of "false", yet you would be in another fault model, where the attacker can do two faults... Now, there are other ways which would render the second fault even harder for the attacker:

The first way is described by Thomas Pornin himself in RFC6979 section 3.6 (emphasis mine):

  Additional data may be added to the input of HMAC, concatenated
  after bits2octets(H(m)):

     K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) || k')

  A use case may be a protocol that requires a non-deterministic signature algorithm on a system that does not have access to a high-quality random source.  It suffices that the additional data k' is non-repeating (e.g., a signature counter or a monotonic clock) to ensure "random-looking" signatures are indistinguishable, in a cryptographic way, from plain (EC)DSA signatures.
  In [SP800-90A] terminology, k' is the "additional input" that can be set as a parameter when generating pseudorandom
  bits.  This variant can be thought of as a "strengthening" of the
  randomness of the source of the additional data k'.

This is the way chosen by XEdDSA, used in Signal, to prevent faults to have an impact on its security. It allows for both the additional security of deterministic ECDSA against biased random sources, still appears perfectly compliant with ECDSA, and will be effective against fault attacks as described in the XEdDSA document. But then you don't get the determinism of the signatures anymore, sadly.

A second way to achieve this same goal might be to sign twice the same data and compare the output of both, if they match to proceed, otherwise there was a fault or multiple unsynchronized faults in the computations. This has the benefit, especially for EdDSA, to not bear the cost of a complete verification, since verification is a way more costly operation there (it also more costly for ECDSA). But still renders the process twice as slow.

A third possibility would be to use so-called "infective" countermeasures as introduced for RSA so that a fault in any part of the final computation would randomize the faulted output. Here is a recent paper (published for FDTC 2017) featuring such a countermeasure for EdDSA. Such a countermeasure would typically combine two different implementations of the same hash in a way that allows recovering the correct value if both output the same data, but would otherwise give nothing of interest. But it is very "local": it might not protect against faults occurring at other steps of the signature process.

I personally like adding back randomness into deterministic ECDSA, which I find both elegant since it's indistinguishable from standard ECDSA and efficient since it bears almost no cost in practice, unlike many other ways.

PS: by the way, Barenghi and Pelosi say that EdDSA shows a structural resistance against these kinds of attacks, but this is actually not the case since it's still possible to obtain sufficiently secret material to mimic valid signatures in a way that only the secret key's owner can detect.


Pollard's kangaroo attack on Elliptic Curve Groups Let's say I've intercepted some bits of a Diffie-Hellman private key: $x = n \mod r$. I can get the remaining bits by doing a kangaroo search. This algorithm works over $\mathbb{F}_p$. Can it be adapted to the elliptic curve Diffie-Hellman problem?

In the ECDH problem over $\mathbb{E}(\mathbb{F}_p)$, we're trying to solve $y = x \cdot G$, where $G$ is a base point for the group. With the private key that I have so far, I have the following transformation:

$x = n \mod r \rightarrow x = n + m \cdot r$

$y = (n + m \cdot r) \cdot G = n \cdot G \oplus m \cdot r \cdot G$

So I want to solve $y' = m \cdot G'$ for $m$, where $y' \equiv y \ominus n\cdot G$ and $G' = r\cdot G$, and $\ominus$ is subtraction of points on the curve.

Basically, is the idea to replace exponentiation in the DH kangaroo algorithm with scalar multiplication, and multiplication in the DH kangaroo algorithm with group addition?

$y_{i+1} = y_i G^{f(y_i)}$ in the DH problem, vs.

$y_{i+1} = y_i \oplus (f(y_i) \cdot G)$ in ECDH?

There are faster ways to do scalar multiplication on elliptic curve points, such as the Montgomery ladder, but that only gives you the x-coordinate of the scaled point.

Do I have the right idea about translating this algorithm to the ECDH? Let's assume that I know about Pollard's rho, Shanks' baby-step-giant-step, etc., but that I really want to get this kangaroo working (er, hopping).

It turns out that, yes, the algorithm applies to ECDH. It can be found in 19.6 of Handbook of Elliptic and Hyperelliptic Curve Cryptography.

More details:

For both the tame and wild kangaroo, the ($i+1$)st hop that the kangaroo takes, $w_{i+1}$, is given by

$$ w_{i+1} = w_i \oplus (H(w_{i+1}) \otimes G) $$

Here, $H$ is a hash function, $\otimes$ is scalar multiplication, and $\oplus$ is point addition on an elliptic curve, and $G$ is a base point on the curve.

You can also compute the distance $d_i$ that each kangaroo travels after $i$ steps, with $d_0 = 0$ and $d_{i+1} = d_i + H(w_i)$.

If you want to search for a discrete log in an interval $[a,b]$, let the tame kangaroo lay $N$ "traps", one at each hop. Then set the wild kangaroo loose, starting at $bG$. The hope is that the wild kangaroo will hop into a tame trap. If their paths intersect, we immediately have a solution to the ECDLP.

In the Python code below is a really lame implementation of it the search. I assume there's an available hash function H. p is the prime of the elliptic curve group $\mathbb{E}(\mathbb{F}_p)$, a,b is the search interval $[a,b]$, y and basepoint are parts of the ECDLP to be solved: $y = t\otimes G$. $t$ solves the ECDLP, and the kangaroo search will probabilistically find it. $N$ is the number of iterations.

def kangaroo_search(basepoint, p, y, a, b, N):

  # setting the trap
  x_tame = 0
  y_tame = b * basepoint

  while N > 0:

    x_tame += H(yT) # scalar addition
    y_tame += H(yT) * basepoint # operations are on E(GF_p)
    N = N - 1

  assert y_tame == (b + x_tame) * basepoint

  # wild search
  x_wild = 0
  y_wild = y

  upper_limit = b - a + x_tame
  while x_wild < upper_limit:
    x_wild += H(y_wild)
    y_wild += H(y_wild) * basepoint # operations are on E(GF_p)

    if y_wild == y_tame:
       print "Victory!"
       return b + x_tame - x_wild

  # index not found
  return None


Do I understand HMAC-SHA-xxx and HMAC-SHA-xxx-yyy correctly? I've recently started looking at HMAC, and there a few things that I'm not 100% sure that I'm understanding correctly.  Am I right about these three things?

HMAC-SHA-xxx has an output length of xxx bits
HMAC-SHA-xxx-yyy has an output length of yyy bits
If I have a function that generates HMAC-SHA-xxx output, then I can create a function that generates HMAC-SHA-xxx-yyy output simply by returning the first yyy bits of HMAC-SHA-xxx output.

If I am misunderstanding any of them, how so?

HMAC-SHA-xxx has an output length of xxx bits

That's right, the output of the HMAC function is identical to the output of the hash by default. This is obvious if you take the design of HMAC in consideration.

  HMAC-SHA-xxx-yyy has an output length of yyy bits

Certainly. It has been defined that way in the venerable RFC 2104 - HMAC: Keyed-Hashing for Message Authentication, section 5: Truncated output.

Not many implementations will allow you to specify the output size, so you may have to truncate yourself. Beware that it is best to perform a time-constant compare when verifying a HMAC value if you have to perform the truncation instead.

Using a standardized, truncated version of SHA-2 would be an option if truncation of the hash is not available (e.g. SHA-224 is already a truncated version of SHA-256). It has the disadvantage that the inner security of the hash is lowered together with the output size.

  If I have a function that generates HMAC-SHA-xxx output, then I can create a function that generates HMAC-SHA-xxx-yyy output simply by returning the first yyy bytes of HMAC-SHA-xxx output.

Yes, you'd use the leftmost bits / bytes. yyy would be in bits, so you'd have to devide by 8 (and I would only allow multiples of 8 for yyy).

Beware that the authors of the RFC talk about "recommend" and "propose" in section 5, so the implementation of HMAC-<hash>-yyy seems strictly optional.


Is the output of AES-CBC + MAC the same size as the input? I use AES-CBC and HMAC-SHA256 to encrypt a text file. Will the output be larger in size than the input or will it be the same size?

Is it more secure secure if the size of the output is larger?

AES CBC usually requires padding, such as PKCS#7 padding. This padding is 1 to 16 bytes, 16 being the block size of AES. The HMAC will add 256 / 8 = 32 bytes to the total. Usually you will need to store the randomized IV as well with ciphertext, to allow for reuse of the key, adding another 16 bytes (the block size again). So the total overhead will be about 16 + 16 + 32 = 64 bytes.

You can shave some bytes off of this by using a smaller tag, but don't go below 8 bytes, the more bytes the more security the tag will provide. You can also use a different scheme and calculate the IV instead of sending all of the IV bytes, as long as the IV is unpredictable to an attacker. You may also be able to deploy ciphertext stealing (CTS) to avoid the padding overhead, but not many libraries contain ciphertext stealing in their implementations of AES-CBC.

With an authentication tag provided by the HMAC you will increase the size, and this will of course enhance your security; it adds integrity and authenticity and may even protect confidentiality if (padding) oracle attacks are feasible.

Don't forget to include the IV information in the authentication tag, and perform the HMAC over the ciphertext instead of the plaintext.


Is every pseudorandom generator a one way function? $$\{G:\{0,1\}^n\rightarrow\{0,1\}^{2n+1}\}^\infty_{n=1}$$

If above function is a pseudorandom generator then is the same $G$ a one way function. I tried to prove this but failed a lot of time. Would be helpful if someone could provide some insight on this.

Prove by contradiction. Assume that it is not a one-way function and that it can be inverted with non-negligible probability. Use this to construct a distinguisher that can distinguish truly random from $G(s)$ with non-negligible advantage. I leave the rest to you...


Is Salsa20+Poly1305 an AEAD? I see Chacha20Poly1305, XsalsaPoly1305 and AES GCM usually used and mentioned in literature and implementations as AEAD cyphers. My question is that Poly1305 provides authentication and Salsa20 provides encryption, a combination of both can be considered AEAD or not? Even though it is not a standard, does it technically fit the definition of an AEAD?

Yes, it can be implemented as an AEAD cipher, although the common definition uses ChaCha20 instead. ChaCha is a cipher with slightly better diffusion and better performance characteristics; both ciphers are by Daniel Bernstein. If you want to use Salsa instead, then just replace ChaCha20 with Salsa20 - but I would rather not do that.

ChaCha20 / Poly1305 is for instance implemented in a TLS 1.3 cipher suite, which references RFC 8439: ChaCha20 and Poly1305 for IETF Protocols, section 2.8, which defines AEAD_CHACHA20_POLY1305. A well used RFC is a clear indication of standardization.


Is this exponentation or bitwise XOR I'm reading about SRP from this page and came accross the line that says a party computes

  v = g^x

I am unfamiliar with reading cryptography texts. Does this mean gx, or g ⊕ x?

In SRP, v = g^x means $v = g^x \mod p$, i.e. exponentiation modulo a large prime $p$.


Does MAC provide origin authentication? Why not just use symmetric encryption? Let's assume Bob and Alice has a secret key for MAC. If MAC is constructed by the key and the message, that means that both Alice and Bob can construct the exact same message and MAC. So, Bob can claim Alice created certain message, not him. What's the point to use MAC then? Why not just use symmetric encryption?

Non-authenticated symmetric encryption schemes are generally malleable, meaning that an attacker who intercepts a message may be able to modify it even without knowing the key, e.g. by flipping arbitrary bits in it.  A MAC prevents such attacks by detecting any modifications made to the ciphertext.

Also, there are various chosen-ciphertext attacks that work by having the attacker feed bogus ciphertexts to a recipient with the key and observing the responses (such as whether the ciphertext decoded to a valid message or not).  A properly used MAC also prevents such attacks, since the attacker will not be able to generate messages that would pass the MAC check.

Finally, a MAC is also useful for detecting modifications to message metadata, which might otherwise allow replay attacks to be carried out.

Instead of combining a traditional symmetric encryption scheme with a MAC, it's also possible to use a purpose-built authenticated encryption scheme to achieve the same goals, sometimes more efficiently.  That said, many authenticated encryption schemes actually consist of a traditional scheme combined with a MAC, although the combination may be done in specific ways that offer some speed, convenience or misuse-resistance advantages over the generic encrypt-then-MAC construction.

Ps. If you want to be able to prove that a given message was sent by Alice to Bob and not, say, forged by Bob himself, you need a digital signature instead of a MAC.

However, note that, for some applications, the inability to verify a MAC without knowing the shared key can actually be considered a feature, since it provides a measure of deniability — if you're Alice, and your supposedly private conversation with Bob is somehow leaked, a MAC cannot be used to prove that you actually wrote the leaked messages, since anyone who can verify the MAC could also forge it.  In particular, the OTR messaging protocol uses MACs instead of signatures precisely for this reason.


Is the beaufort cipher just as secure as the Vigenere cipher? Does the Beaufort cipher have the same strength as the vigenere cipher assuming you use the same complexity of key, or because of it's reciprocal nature make it less secure?

Yes, it is.  The Beaufort cipher is identical to the Vigenère cipher except that, in effect, the plaintext alphabet is reversed (i.e. mapped A → Z, B → Y, etc.) before encryption (and after decryption).  The reversal adds no appreciable security, but it also cannot make the cipher less secure.


Implement AES with 16 bit block size? Can we implement AES with 16 bit block size ?if so what are its advantages and disadvantages?Is there any rule AES has to be implemented with 128,192,256 ?Can we use AES for odd number of bits(17,33,37..) ?

I am assuming that you wish to consider this for standard encryption tasks, and I am going to ignore the specific reference to AES and talk about general block ciphers (pseudorandom permutations).

The answer is that small block sizes are very problematic. In particular, they break when used for encryption of any reasonable amount of information. I will consider two concrete examples. In CBC mode, security breaks down after $2^{n/2}$ blocks, when $n$ is the block length. This means that you could not encrypt more than $2^8=256$ blocks, which is just 512 bytes. This is due to birthday collisions. However, it's actually worse than this. The probability of having a collision at less than 256 blocks is not so small, and at such small numbers it is very problematic. If you use CTR mode, then once again you have a problem since the nonce/IV has to be unique. Even if you are using this from fresh each time with a new key, and so just use a counter beginning at 0, you still have a problem that you can't encrypt more than $2^{16}$ blocks, which is just 128KB.

Regarding constructing such a small block cipher, this can be done using the techniques from format-preserving encryption. You use a Feistel, but you need many rounds with such a small block (also making it very inefficient). Specifically, you need 24 rounds of Feistel (this is the current recommendation but there is also a concerning lack of clarity regarding the exact security in this case).


Interesting malleability property of Goldwasser-Micali PKC GM is a cryptosystem with a modulus $N = pq$ ($p$, $q$ prime) and quadratic nonresidue $r \in (\Bbb Z / N\Bbb Z)^*$ as the public key. You can see the details on Wikipedia.

Anyway, let's say that $N < 2^{1024}$. Then the ciphertext can be represented as a $1024$-bit string regardless of $N$. In which case, you can take a ciphertext $c$ (which is the encryption of a single bit), and then multiply $c$ by a random $z^2 \pmod{2^{1024}}$, and get an equivalent ciphertext. An adversary should, as far as I can tell, be unable to decide whether this decrypts to the same plainbit as $c$. And you don't need to know the public key $(N,r)$ to do this operation.

Is there any literature on this property?

This property is a consequence of the homeomorphic property of GM (plus the fact you don't need to know $r$ to encrypt a 0).

In GM, given $Encrypt(A)$ and $Encrypt(B)$, you can compute $Encrypt(A \oplus B)$.  This is what the above observation is doing; generating a random encryption of 0, and then computing $Encrypt( A \oplus 0 )$ (which, of course, stands for the same plaintext as did the original $Encrypt(A)$.  Because someone without the private key couldn't tell that your random $Encrypt(0)$ held a 0 or not, they also can't tell whether your new ciphertext has the same plaintext as same as the old.

You can do the same with Pallier; you can encrypt a 0, and then compute $Encrypt(A + 0)$; again, no one without the private key can tell whether the new ciphertext conceals the same value as the old.


Use a hash-function twice I'm creating a small messenger and I wanted to know if it makes sense to store user passwords double-hashed in our backend-database. I wanted the user the register in an app, which should save a hash of the password and login with this hash in our system, which should not save this (1st) hash, but should somehow hash it again.

This would prevent someone who somehow got a (doubled) hashed password from our database from logging in into our api (since he needs to provide the 1st hash) and also would allow the app to not store the passwords of the user in plain text.

Is this a good idea? Should I just stay with the first hash and not hash the password again when using it in our backend-db? I read that something like this might be insecure as hashes become less secure the more often you hash them again. Should I maybe use different hash-algorithms for both actions? Which algorithms should I use?

I read that something like this might be insecure as hashes become less secure the more often you hash them again.

While this is technically true, you shouldn't worry about it. This paper has precise bounds on how bad it is to iterate a random function and with the iteration count $r<10$ as you are worrying right now this is a non-issue for security.

  This would prevent someone who somehow got a (doubled) hashed password
  from our database from logging in into our api (since he needs to
  provide the 1st hash) and also would allow the app to not store the
  passwords of the user in plain text.

This is a good idea and also the ideal model of how client-side password hashing is supposed to work: You compute an (expensive) password hash on the client, send it to the server who then hashes (or somehow else one-way processes) it so that an attacker leaking the database doesn't get all the log-in hashes for free.

  Should I maybe use different hash-algorithms for both actions?

Yes. As explained in the previous paragraph, you want to use a slow password-hashing scheme on the client, like Argon2 and then you can use a fast (normal) hash function on the server, like SHA3-256.


How good is using AES CTR mode with initial counter as 0? Is it advisable to use AES CTR mode with the counter initialized to 0? How good is it in security terms?

As long as you never re-use a specific counter value with the same key, counter mode protects the privacy of the message.

All counter values are equally secure. You just have to be sure never to re-use any counter value in two different messages. Zero is no different to any other counter value in this respect.

However, if you ever re-use any counter values then the secrecy of both messages is completely lost.

If you plan to encrypt many messages under the same key, then it would be wise to choose a different counter strategy to avoid the possibility of re-using counter values.

One such strategy is to allocate the first 64-bits of the block to the milliseconds since 1970. This is safe if the key is only used in a single thread and you don't encrypt more than one message per millisecond. This won't take the full 64-bits, so you can just fill the remaining bits at random. You then reserve the remaining 64-bits for the counter. This will make it difficult for two messages to use the same counter values.


How does one measure the decrease in security, if any, of RC4 when mapping to a specific range of values? For a project using RC4, the output is to be mapped to values of 0 to 35.  Thus, only 36 unique output values representing the letters A to Z and 0 to 9.

To avoid bias, the RC4 byte output (with a range of 0 to 255) is discarded if the value is greater than 251.  The output is then mod 36, which then maps the output into the range of 0 to 35.

Does this effectively reduce the strength of RC4 by taking this mapping step, or does the security remain unchanged?  How does one measure the amount of decrease in the security?  Does it relate to the loss of the values 252, 253, 254 and 255?  Or, would it also be a factor of doing the mod 36 step because of reducing the possible output values to 1/7th of the original.

Thanks!

By discarding values 252 to 255, you effectively avoid introducing any new bias; the generic method is expressed in many places, e.g. this article (page 3). To generate random values between $0$ and $d-1$ (inclusive) from a PRNG which produces bit, you do the following:

Choose an integer $r$ such that $2^r \geq d$.
Obtain a $r$-bit word $x$ from the PRNG.
Compute $t = \lfloor \frac{x}{d} \rfloor$.
If $d+td \gt 2^r$, go back to step 2.
Output $x - td$.

Your proposal is equivalent to the algorithm above with $d = 36$ and $r = 8$ (you work with 8-bit words, colloquially known as "bytes").

There are trade-offs about the choice of $r$, which depend on what the hardware and software can do. On an 8-bit CPU with very little power, using bytes is certainly efficient, but involves either doing a division (which will be expensive in CPU time) or using a lookup table with 256 entries (so 256 bytes of ROM -- probably tolerable, since RC4 itself requires 256 bytes of RAM, and RAM is much more expensive than ROM). Speaking of which, RC4 is not necessarily the best choice, performance wise: there are other stream ciphers worth considering.

Note that even though your method does not introduce any bias, you still have the shortcomings of RC4, namely some detectable biases in the raw output (nothing lethal in practice, but enough to give the willies to academic cryptographers), and the absence of any IV, which means that you need a new key for every generated stream (if your messages are consecutive and serialized, you can consider them all as parts of a single big stream, but each new session / reboot MUST imply a new key; otherwise that's the infamous "two-times pad").

36 is for letters and digits; for general messaging you might want to add a few signs for spaces and basic punctuation (at least a word separator).


Fully Homomorphic Encryption over the Integers - Runtime Question I have a question regarding the paper "Fully Homomorphic Encryption over the Integers"
(http://eprint.iacr.org/2009/616.pdf): On page 6 after they set their parameters, it says

"This setting results in a scheme with complexity $\overset{\sim}{\mathcal{O}}(λ^{10}).$"

What exactly do they mean by this? That the runtime is $\overset{\sim}{\mathcal{O}}(λ^{10})$? If yes, the runtime of what exactly - performing a multiplication on encrypted data? After all, the overall runtime of the scheme depends on the depth of the circuit that is being evaluated, so such a generic bound on runtime of the whole scheme would not make much sense, would it?

My second question (which assumes that "complexity" refers to runtime) is the following: In section 5 (page 13), the authors present an attack which has running time $2^{2\rho}$, where $\rho = \omega(\log(\lambda))$. Wouldn't that make the attack in general much faster than the runtime of the scheme? On page 6, it says that "A convenient parameter set to keep in mind is $\rho = \lambda,$ [...]", in which case I understand why we do not need to worry about the attack, as it runs exponential in $\lambda$. But is it really enough to require $\rho = \omega(\log(\lambda))$ in general, or wouldn't values of $\rho$ that are very close to $\log(\lambda)$ make this scheme extremely unsafe? Also, does $\overset{\sim}{\mathcal{O}}(λ)$ mean linear in the bitlength of $\lambda$, whereas $2^{2\rho}$ refers to the actual numerical value of $\rho$?

I looked at runtime tables here: http://eprint.iacr.org/2011/440.pdf (where both the scheme and the attack have been slightly modified) and the scheme is way faster than the attack, even though they chose $\rho$ smaller than $\lambda$. Although not logarithmically smaller, I actually have no idea how they derived $\rho$ from $\lambda$.

So am I missing something, or is everyone just using $\rho \approx \lambda$ and the bound $\rho = \omega(\log(\lambda))$ is not safe?

On the first question

The public key of DGHV's SHE scheme consists of $\tau+1$ $\gamma$-bit numbers, that is, $pk = (x_0,\dots,x_\tau)$, where $x_i$ is chosen from the distribution $\mathcal{D}_{\gamma,\rho}(p)$ over $[0,2^{\gamma})$.
Therefore, the length of $pk$ is $O(\tau \gamma)$, which is $\tilde{O}(\lambda^{10})$ if we adopt the parameters $\gamma = \tilde{O}(\lambda^5)$ and $\tau = \gamma + \lambda$ as the authors said.

In order to encrypt a bit $m$, we sample a random subset $S$ and a "relatively small" integer $r$, and compute $c = m + 2r + 2 \sum_{i \in S} x_i \bmod{x_0}$.
Here, we have to read the whole of the public key and the main task is adding $x_i$ randomly. Hence, the complexity of encryption is $\tilde{O}(\lambda^{10})$, which is the result of $\tau$-time addition of $\gamma$-bit integers.

In order to multiply two fresh ciphertexts, which are $\gamma$-bit integers,
we require about $O(\gamma^2)$ bit operations. (By using more sophisticated multiplication, it is reduced to $\tilde{O}(\gamma)$.)

As you said, the time of evaluating a circuit and encrypted data mainly depends on the depth of the circuit.
Getting worse, we are often required to adopt the FHE scheme and "refresh" intermediate ciphertexts.

On the second question

As an example, we take $\rho = \log^{2}(\lambda)$.
This results in $2^{2\rho} = \lambda^{2 \log(\lambda)}$, which is asymptotically greater than any polynomial of $\lambda$.
Hence, asymptotically speaking, the attack is not faster than the runtime of the scheme.
As you thought, if we take $\rho$ is very close to $\log(\lambda)$, the scheme is unsafe for small $\lambda$.


How was the MDS matrix used in AES chosen? $$\begin{pmatrix}2&3&1&1\\
1&2&3&1\\
1&1&2&3\\
3&1&1&2\end{pmatrix}$$
In the above MDS matrix used in AES encryption, why are the numbers $2$,$3$ and $1$ chosen? Why not any other number?

They were chosen because they are the smallest non zero elements possible that make the matrix MDS and circulant. With an MDS matrix, if a single input changes, all the outputs change.

When multiplying the matrix by a value, you need to multiply the input bytes by the values of the matrix in a finite field. These multiplications have a computational cost associated with them that is related to how large the matrix values are, therefore keeping them as small as possible is a design criteria for efficiency.

Multiplication by 1 is obvious, but in the finite field used by AES, multiplication by anything else is different, since you are treating the values as polynomials.

When implemented, multiplication by 2 is a left shift with a conditional XOR, multiplication by 3 is multiplication by 2 plus XOR against the original value. Other larger numbers require more operations. Having the matrix be circulant also allows efficient operation, since you only need to perform a single multiplication per input element, and the rest is all XOR.

Multiplication can also be done in advance then use a table lookup, but that is not good for devices with very low RAM and ROM. Having the elements be small keeps the performance good for when a table lookup implementation is neither optimal nor possible.

A similar circulant MDS matrix with values 1,1,7,4 is used in the Fugue hash function which requires 2 multiplications per input element. Twofish uses 1,91,239 in a non-circulant matrix.


Is this ECC based messaging method secure? I developing an encrypted messaging for ZeroNet (aP2P file-based network, website: zeronet.io) and would like to have some guidelines if any of this could work.

My first idea:

In ZeroNet every user has his/her own files signed by ECC this ensures the messages authenticity.
When Bob visits the site first time then a new (Bitcoin BIP32 based) public key will be generated, written to his file, signed and published to the network.
If Alice want to message to Bob then reads the Bob's public key, creates a new message using ecc_encrypt_using_bob_pubkey("ZNE1" + generated_aes256key + generated_aes256iv + aesencrypted_text), puts it to her file, sign and publish to network.
If a new file is published to the network then Bob checks the added messages in it and try to decode them using his ECC privatekey.

To make privacy better the sender does not specify the messages recipient, so have to check every messages added to the network.
The messages are signed with one ECC private key and encrypted with an another one.

My other idea:

If Alice wants to send a message to Bob, then she puts ecc_encrypt_using_bob_pubkey("ZNE1" + generated_aes256key + generated_aes256iv) encrypted shared secret to her file. (or better to use per-message, unencrypted IV?)
Then from now Alice will use this shared secret to encrypt messages to Bob (random prefix + protocol id + message)
If a new file is published then Bob checks encrypted shared secrets in it and see if he able to decrypt any of them.
If he successfully decrypt a shared AES secret from Alice file then he checks Alice's encrypted messages and decrypt the messages in Alice file.

The pros of second idea:
 - Shorter messages
 - Don't have to store the messages twice (one for other user, one for our sent folder)
 - AES provides 100x faster message checking.

The cons of second idea:
 - If the AES key is broken then all messages can be decrypted (applies both if privkey broken).
 - Anyone able to see if you added a new shared secret (start messaging with new people)

Thanks for any suggestions!

You should consider “sign-then-encrypt” instead of “encrypt-then-sign”.

Note that it is very important that the “encrypt” in “sign-then-encrypt” should be authenticated encryption. If you don’t use authenticated** encryption, you should definitely use an athenticating “sign-then-encrypt-then-MAC” approach.

Besides that:, when thinking about all this, you should definitely keep ECIES and ECDSA in mind.


What is this encryption system called? Let's say you want to break down a message, for simplicity it is just a bit $0$ or $1$, $m$ into two messages $(m_1, m_2)$ as follows:

If $m =0$, then $(m_1, m_2) = (0, 0)$ with probability $1/2$ and $(m_1, m_2) = (1,1)$ with probability $1/2$. Similarly, if $m=1$, then $(m_1, m_2) = (0,1)$ or $(1,0)$ each with probability $1/2$.

It's clear how the message can be retrieved from the two messages, and that nothing can be know from a single daughter message (each will be 0 or 1 with equal probability regardless of the mother message), unless the random number generator has a bias of sorts.

What is this system called?

(I don't do cryptography by trade, don't know which tags to use.)

You could view it as a form of One-Time-Pad encryption. In this view one of the two "messages" is the key and the other is the ciphertext (it does not matter which you think of as which as their roles are symmetric).

It may, however, be more natural to think of as a simple secret sharing scheme. Roughly speaking a secret sharing scheme is a scheme where a secret is divided into a number of shares. Usually you then need more than some specified number of shares to reconstruct the secret, and any lower number of shares will give no information on the secret.

For your scheme $m$ is then the secret, $m_1$ and $m_2$ are the shares and you need both shares to reconstruct the secret.

The scheme you describe is a well known and much used one, sometimes referred to as "XOR" sharing. This because you can define the shares as picking random bits $m_1, m_2$ under the restriction that $m = m_1 \oplus m_2$.


Password protected Excel files I need to send an Excel file to someone, normally I would use encrypted e-mail, however, this is not an option with this individual. What is the minimum length password I can apply to this file to get a decent level of protection and is there a way to mathematically compute the strength of a password?

Excel 2007 (12.0) and up uses an iterated hash and AES encryption by default if you use the native, non-backwards compatible XML format (.xlsx), so the weak point is for sure the password. Depending on how safe you need to keep the document, you can use simple passwords, or you can use more complex character sets and combinations of words. If you are using an earlier version of Office or not using the .???X file format, assume it is insecure.

The encryption process itself uses with Windows crypto provider, and the default settings are generally secure; AES 128-bit encryption in CBC mode on 4KB chunks of data, the OS random number generator for salt and IV based on that salt, and an iterated hash (at least 50000) based on SHA-1 or SHA-2, depending on the version of Office. These settings be changed, if you are concerned I would suggest checking the encrypted document, the XML format will define the type of encryption used.

For high security, I require an 80-bit strong password. If you are using random characters from the default alphanumeric 62 character set, a secure password length is 14 characters, and would be considered unbreakable by normal means, 22 characters would match the strength of AES.

If your password is NOT random characters (rather actual words or phrases), then there are methods to estimate password strength, but they can be very inaccurate, usually telling you it is stronger than it really is. Easy to remember words and phrases are generally easier to crack, the algorithms used by password cracking software are quite effective at cracking even long passwords if the password is not random.

If you need actual words, I suggest you choose at least 6 random words from the dictionary that are at least 5 characters long. You can also use the PGP wordlist, which allows you to easily use bytes from a random number generator to get them. You would need at least 10 words to be secure, and 16 to match the strength of AES. Other wordlists are acceptable, such as the diceware list, if you are aware of how much strength there is per word (12.9 bits for diceware).


What other one-way functions are used in cryptosystems? For RSA and El Gamal (and most other public key cryptosystems), one of the key ideas is that factoring and finding discrete logarithms are hard. There are other systems that rely on certain properties of lattices.

What are the other one-way-ish functions that have cryptosystems designed around them?

The Merkle–Hellman knapsack cryptosystem was based on a variation of the subset sum problem.  (It was broken by Adi Shamir a few years after it was developed.)

  Given a set of numbers $A$ and a number b, find a subset of $A$, which sums to b.

The cryptosystem relies on the fact that in this form of the subset sum problem if the set $A$ is superincreasing (each element of the set is greater than the sum of all the previous elements), the problem is solvable in polynomial time.  Also, you can transform the superincreasing set $A$ into a non-superincreasing set $B$ using a multiplier $r$ and a modulus $q$.

Solving the subset sum problem with a non-superincreasing set ($B$) is NP-complete, so you can use $B$ as a public key to encrypt messages, then use $A$, $r$, and $q$ as a private key to decrypt them.


Demonstrating Diffie-Hellman key exchange using only p, A, B; I'm trying to figure out how to demonstrate DH key exchange using what is given to me. I'm unsure of how to tackle the problem.

Question:

Demonstrate Diffie-Hellman key exchange.

Given p=104933, A=324, B=5832. Prime factors for p-1 {2,37,709}

A and B are Alice and Bob secret keys respectively.

What is the value of the shared key?

Process to solve:

So there are 5 steps to DH key exchange.

Alice and Bob share prime p and generator g
Alice sends g^a mod p to Bob
Bob sends g^b mod p to Alice
Alice computes the shared key
Bob computes the shared key

I get stuck at step 1 though because I'm unsure of how I'm supposed to find the generator given this information.

I guess the problem is to find the generator $g$.

Denote the factors for $p-1$ to be $p_1 =2, p_2 =2,p_3 = 37, p_4 = 709$.

With $p$, and the factorization of $\phi(p)$ you can find a generator in the following way:

Randomly choose an element $x$ from $Z_p$ and test whether $x^{\phi(p)/p_i}$ mod $p \ne 1$ for every $i =1,2,3,4$. If this is the case, $x$ is a generator. Otherwise, just select another element to run the test. You should find one soon. (Please refer to wikipedia for the method.)

Since $5^{2\times 37 \times 709}$ mod 104933 = 104932, $5^{2\times 2 \times 709}$ mod 104933 = 45751, $5^{2\times 2 \times 37}$ mod 104933 = 92770. Then 5 is a generator.

Next steps are basic algebra, I will stop here.


Can Curve25519 be used for pairing-based cryptography? We usually need pairing-friendly curves in order to use them for bilinear pairing computation. Is Curve25519 a pairing-friendly curve? If not, can we still use it for pairings and how much more inefficient would a pairing computation on this curve be compared to a BN curve?

The embedding degree specifies how many times bigger the finite-field you map to is compared to the field the curve is defined over.

For example for BN(2,254) the degree is 12, mapping to a 3000 bit field, which matches the security level of the curve (~128 bits of security for both) and is reasonably efficient (you can perform a couple of hundred exponentiations per second in this field).

For Curve25519 the degree is 1206167596222043702328864427173832373476186059896651267666991823047575708498 $\approx 10^{75}$, mapping to a $\approx 3 \cdot10^{75}$ bit field. It's rather unlikely that you could afford a computer which can store an element of this field or perform computations on it.

https://safecurves.cr.yp.to/transfer.html


Point multiplication twice - can it be squeezed into one equation? p_1 := (d_1)G
p_2 := (d_2)p_1

$P_2$ is calculated as shown above. Will $P_2$ be the same of $P_2$ in the second equation?

p_2 := ((d_1 * d_2) % curve_order)G

If I understand correctly, it shouldn't have any problems with the point at infinity. Are there any differences between two ways to calculate the point?

Yes, on an elliptic curve $\mathcal C$, we can use that $\forall d_1\in\Bbb Z, \forall d_2\in\Bbb Z, \forall G\in\mathcal C$
$$\begin{align}
d_2\times(d_1\times G)&=(d_2\cdot d_1)\times G\\
&=(d_2\cdot d_1\bmod n)\times G
\end{align}$$
where $n$ is the order of the curve, and also for $n$ the order of $G$ (which divides the order of the curve). That more generally holds in any finite group $(\mathcal C,+)$ with scalar multiplication $\times$ defined from the group law $+$ (even if not commutative).

For $d_1$ and $d_2$ random in $[0,n)$, the form $(d_2\cdot d_1\bmod n)\times G$ will typically be fastest, for decent implementation of the modular multiplication. It is best to use $n$ the order of $G$ (which can be smaller than the order of the curve). Beware that the modular multiplication could lead to a side channel.

If $d_1\times G=\infty$ with $G\ne\infty$, and the implementation of $d\times X$ fails when $X=\infty$, then both $(d_2\cdot d_1)\times G$ and $(d_2\cdot d_1\bmod n)\times G$ will prevent that failure (the end result will be $\infty$ all the same and the implementation should be able to deal with this). If the implementation fails when it internally encounters $\infty$ in some internal operation, the change in method of computation can potentially remove or create the condition triggering the issue; that depends on internals.

I have used $\cdot$ for integer multiplication, and $\times$ for point multiplication by scalar/integer.


order between adversaries and type of resources given We have a game $G0$ for which an adversary $A$ has access to a certain amount of ressources. Let us suppose that the maximum advantage for the adversary to win this game is $Adv_{G0}$.

If we modify slightly the game $G0$ into the game $G1$ in such way that we give an additional information (useful or not) to this adversary.

Can we state that $Adv_{G0} \le Adv_{G_1}$ ?

If we consider indistinguishability games for encryption, the first one with CPA attack, the second one with CCA attack. Can we state that $Adv^{CPA} \le Adv^{CCA}$ ?

Can we state that $Adv_{G0} \le Adv_{G_1}$ ?

Absolutely.  Let us call $S0$ the strategy that $A$ can use in game $G0$ to achieve advantage $Adv_{G0}$; we notice that $A$ can also use strategy $S0$ to achieve that exact same advantage in $G1$, and hence we see that the maximum advantage he can achieve in $G1$ must be at least as large as in $G0$

  Can we state that $Adv^{CPA} \le Adv^{CCA}$ ?

No (unless we assume that, in the CCA case, the attacker is also allowed to submit chosen plaintexts as well).

To demonstrate this, construct an encryption method that is secure, except that if the plaintext was the specific message "Open Sesame", it outputs a ciphertext that is the encryption key.

In this case, $Adv^{CPA}$ is quite large (the attacker submits two plaintexts, one "Open Sesame" and one something else, and see if the key he got from the "Open Sesame" message encrypts the other message in the ciphertext he got).

However, there is no obvious way that the attacker can use chosen ciphertexts; he knows that if he submits a ciphertext that happens to be key, he'll get the plaintext "Open Sesame"; however that doesn't help him, as there are other ways to verify a guess on the key.

Hence, in this artificial example, we have $Adv^{CPA} > Adv^{CCA}$


One cipher to rule them all? I learned from Dan Boneh's course that many cryptographic primitives (prngs, stream ciphers, hashes, hmac, key derivation functions) can be built from just one a block cipher or PRF.

For example, the sha-1 hash is based on a compression function which can be used to make a block cipher SHACAL-1. More generally a Hash from a block cipher using Davies-Meyer construction.

There was a question SHACAL-2 vs. AES as underlying block cipher for Secure Hash (aka SHA-256) which explained some points about why AES is not suitable to base a hash on.

My question is: Is there a single block cipher or PRF (or other basic primitive) which is suitable to construct the other primitiveness from?

I looked into the simon and spec ciphers (PDF) for this purpose but they say:

  We have made no effort to guard against attacks in the open-key model, and Simon and Speck have not been evaluated for use as hashes.

This question is based on opinion. At least kind-of. But the variants from which one can choose are quite a few.

As for general construction the sponge construction (like Keccak / SHA-3 uses) are very versatile and can be used for many purposes, for example hashing, authenticating (= "MAC'ing"), authenticated encryption (see “General Overview of the First-Round CAESAR Candidates for Authenticated Encryption”, Version of March 14, 2015 by Farzaneh Abed, Christian Forler, and Stefan Lucks).

Of course one can also use such constructions or already exisiting construction to construct the rest, PRNGs may use hashes at some point, stream ciphers can be hashes in counter-mode, HMAC can use sponge-based hashes, KDFs can be based on sponge-based hash functions, using the arbitrary output size and tweaking the input for other parameters.

Now if you're specially looking for one cipher / hash-function which can be used without much effort in a variety of modes, I think (and others as well as the comments suggest), that Threefish is the cipher to choose. Threefish was designed as a building block for a hash-function, meaning all known attack scenarios were considered, like standard attacks and related-key attacks. Threefish and it's associated hash-function Skein can also be used in a variety of modes:

Threefish can of course be used as a standard block cipher. (Maybe set the tweak to $0$?)
Skein, which is a lightweight construction around Threefish, can be used as a standard hash-function.
Skein-MAC, a mode of operation for Skein, is a provably secure MAC (like HMAC).
Skein-HMAC, Skein can of course also be operated in the standard HMAC construction.
Skein-KDF, a mode of operation for Skein, is a highly customizable variant of Skein, using the fact that Skein can output arbitrary sized digests.
Threefish stream cipher. Threfish can be used as a standard stream cipher in CTR-mode.
Skein stream cipher. Skein has a mode of operation allowing it's output to be used as a stream cipher pad.
Skein-PRNG is proposed in the original Skein paper. I'd recommend against using it but rather use Skein and Threefish within Fortuna instead of AES and SHA-256.
Skein-PBKDF is a PBKDF2-like mode of operation for Skein. I'd recommend against using it but rather use scrypt, bcrypt or any of the PHC-winners (to be announced). Some of the finalists allow usage of arbitrary hash-functions, where Skein could be used.
Threefish authenticated encryption is a bit more tricky, but there are a few schemes that use tweakable block ciphers (like Threefish) to construct fast AEAD ciphers.


secp521r1 elliptic curve base point coordinates According to Standards Recommanded Elliptic Curve parameter for Cryptography, for each given curve, the base point is given in compressed and uncompressed form, but personnaly I do not understand how to use it with that form, I need the (X,Y) coordinates for my application, thanks to show me how to find them from the given form.

The compressed form of the base point only provides the X coordinate. It is identified by a leading $\mathtt{02}$ or $\mathtt{03}$ byte. The remaining bytes are the hex-encoded X coordinate. Y can be recovered using the curve definition $y^2 = x^3 + ax + b \pmod{p}$. As both Y and -Y can satisfy the equation, the leading $\mathtt{02}$ indicates the that the positive value should be taken, and the leading $\mathtt{03}$ indicates that the negative value should be taken. You can read more details in this answer.

The uncompressed form of the base point provides both the X and Y coordinates. It is identified by the leading $\mathtt{04}$ byte. The remaining bytes are the hex-encoded X and Y coordinates, concatenated as X || Y.

Looking at SEC2 Ver1, "2.9.1 Recommended Parameters secp521r1", we have:

G =       04 00C6858E 06B70404 E9CD9E3E CB662395 B4429C64 8139053F
    B521F828 AF606B4D 3DBAA14B 5E77EFE7 5928FE1D C127A2FF A8DE3348
    B3C1856A 429BF97E 7E31C2E5 BD660118 39296A78 9A3BC004 5C8A5FB4
    2C7D1BD9 98F54449 579B4468 17AFBD17 273E662C 97EE7299 5EF42640
    C550B901 3FAD0761 353C7086 A272C240 88BE9476 9FD16650

In other words, the uncompressed encoding of the basepoint G = 04 || X || Y. Using that we can parse the coordinates of G as:

X =     00C6 858E06B7 0404E9CD 9E3ECB66 2395B442 9C648139 053FB521
    F828AF60 6B4D3DBA A14B5E77 EFE75928 FE1DC127 A2FFA8DE 3348B3C1
    856A429B F97E7E31 C2E5BD66
Y =     0118 39296A78 9A3BC004 5C8A5FB4 2C7D1BD9 98F54449 579B4468
    17AFBD17 273E662C 97EE7299 5EF42640 C550B901 3FAD0761 353C7086
    A272C240 88BE9476 9FD16650


Entropy Requirements for Encryption Quality of RNGs is an important issue.

As a very basic question I would like to understand, how "poor" entropy of a RNG can help an attacker to find out the whole secret.

In my naive view, even is a RNG (e.g. of 128 Bit) is not perfect in terms of entropy, but deviates, lets say ~0.1 % from the perfect value 128, so that it has only Entropy 127, how can an attacker find the key? Guessing the remaining 127 Bits would also be an infeasible task - ??? So what can he practically do?

I would also appreciate a good source for reading.

thanks ;-)

For example, assume an RNG spits 128-bit values $X$ that are all-zero with odds $p=1/120$, and otherwise independent and evenly distributed among the other values. The 128-bit values spit by this RNG contain $H(X)=-p\log_2(p)-(1-p)\log_2\big((1-p)/(2^{128}-1)\big)>127$ bits of entropy.

Yet, if repeatedly the same secret is XOR-ed with this RNG forming 128-bit ciphertext blocks, the secret can be recovered, with overwhelming odds, as the first value that repeats; and there are better than even odds that this occurs with a mere 250 ciphertexts.

Another example would be a 128-bit RNG where each bit is independent with odds $p=9/20$ to be one, for $H(X)=-128\big(p\log_2(p)+(1-p)\log_2(1-p)\big)>127$ bits of entropy.

With the same hypothesis as in the first example, the secret can be recovered by keeping the most frequent bit value for each rank. Few hundred ciphertexts are enough to recover the secret with fair odds.

Note: the generator of the second example is still safe to generate AES-128 keys; while the first is disastrous; which illustrates that entropy is not the only thing that matters for a RNG.


A single password manager vs password generator/hash I have been wondering about the options available for managing passwords. However, they all seem to fail if the master password is compromised (which isn't a big surprise).

On one hand you have system's like LastPass which store all your passwords using a master password to encrypt them.

  In other words, your computer encrypts your passwords with your email and master password and sends that data to Lastpass. When you authenticate with your master password at Lastpass.com, Lastpass.com returns all your encrypted passwords, which are decrypted locally on your computer with your email and master password.

On the other hand you have systems which take a master password and then can generate a unique (but always the same) password by adding the domain or other identifier. This is perhaps more safe in one way since nothing is ever stored or transmitted anywhere. However, it's less safe in another way since you can never change an individual site's password if it is ever compromised.

In both cases it seems that knowing the master password either gives you the other passwords, or allows you to generate them. Are their any other options? Am I missing any other large security problems these password managers create?

Let's look at the risks.

Encrypted password database

To steal your passwords, the attacker has to steal the database. Then she has two options: steal the master password or guess/bruteforce it. Once the attacker has the database and master password, she has access to your current accounts until you change stored passwords.

Password generator (from a single master password)

To steal your password, the attacker has to steal your master password, or steal one of the derived passwords and guess/bruteforce the master password. Once she has it, she can generate any current and future passwords, until you stop using the generator with the same master password. Thus, using the password generator scheme (with at least one compromised derived password or the ability to quickly check derived password guesses) is roughly equivalent to the encrypted database scheme where the attacker has permanent read-only access to the encrypted database.

* * *

There are other problems with the second scheme: most password generators I've seen are insecure: they use fast hash/HMAC to generate passwords. Thus, if your master password has low entropy, it's easy to bruteforce it.

The most sensible password generator I've seen is described in this paper: A Convenient Method for Securely Managing Passwords
. It uses a very slow hash to generate a secret seed from master password and stores it. It then hashes the master password again with a faster hash function, combines this hash with the stored seed and derives passwords from the result. This considerably slows down bruteforce attacks.

  However, it's less safe in another way since you can never change an individual site's password if it is ever compromised.

It's possible to change passwords generated by the second scheme: just add some counter to the domain (e.g. "example.com" -> "example.com:2"), though this isn't convenient, as you have to remember the counter.

  In both cases it seems that knowing the master password either gives you the other passwords, or allows you to generate them. Are their any other options? Am I missing any other large security problems these password managers create?

Unless you can remember many random passwords, using open source offline password manager with encrypted database (with correctly implemented encryption and key derivation) is probably the most secure scheme available. However, there are factors other than security to consider, for example, risk of losing the database, convenience, etc.

* * *

The linked password generator is insecure (even if used offline) if the master password has low entropy: it uses a single round of HMAC-SHA256 to derive passwords.


How to to calculate the hash of an unordered set Suppose I have a set of elements, with known hash (e.g. SHA-2). How can I calculate the hash of the set? With it I mean an unordered set, so the order of elements is undefined and shall not play any role in determining the hash of the set.

In theory any commutative operation applied to the hashes should be fine, but I have the strong feeling that XORing all of them together is quite unsafe. An attacker could add an element to the set to produce a hash collision, although finding an element with that wanted hash is as hard as breaking the hash of the whole set.

Anything better solution than the trivial one of sorting the elements into a list, calculating their hashes and then calculating the hash of the hash list?

I think Merkle trees can't help here if they are based on some sort of ordering of the elements.

A well known technique to form the hash of an unordered set given hashes of the elements, is to order the hashes lexicographically, concatenate them in this order, and hash the result. The order of the elements in the original set does not influence the result, and this demonstrably inherits the properties of the hash (collision-resistance, preimage resistance, security in the ROM). The reader is left to decides if this is the trivial one of sorting the elements. That has serious drawbacks: the hashes must be stored; this is not an online algorithm.
This would be fixed by XORing the hashes of the elements of the set, but (as conjectured in the question) this gives a weak hash. In particular, if the hash is $b$-bit, then after a little more than $b$ elements we likely can find $b$ hashes that are linearly independent (w.r.t. bitwise XOR), and then by XORing some of these hashes we can form any value desired; that's a first-preimage attack.

Update: Meir Maor's comment pointed this very relevant paper: Dwaine Clarke, Srinivas Devadas, Marten van Dijk, Blaise Gassend, G. Edward Suh, Incremental Multiset Hash Functions and Their Application to Memory Integrity Checking, in proceedings of AsiaCrypt 2013. It builds hash functions for multisets, and their results apply directly to sets, which are multisets with multiplicity restricted to $\{0,1\}$ .
Based on their MSet-Mu-Hash construction, the following works, requires no sorting, and can be computed  with constant memory as the hashes of elements of the set are made available to an online algorithm:

Choose a nothing-up-my-sleeves 2049-bit public prime $p$ with $(p-1)/2$ also prime, e.g. $p=\lfloor2^{2047}\pi+494382\rfloor$ ; we assume the discrete logarithm modulo $p$ is hard, about as much as breaking SHA-256 collision resistance.
Expand each given SHA-256 hash $H_i$ of an element of the set into a 2048-bit bitstring $S_i$, e.g. as $S_i=\operatorname{H}(H_i\|K_1)\|\operatorname{H}(H_i\|K_2)\|\operatorname{H}(H_i\|K_3)\|\operatorname{H}(H_i\|K_4)$ where $\operatorname{H}$ is SHA-512 and the four $K_j$ are short distinct public arbitrary constants.
Compute the product modulo $p$ of the $S_i$ (converted to integer per big-endian convention); this can be done jointly with the previous step. The product will be $1$ for the empty set.
Hash the product (converted to a 2056-bit string per big-endian convention) with SHA-256 in order to produce the final result.

Note: in order to avoid certain attacks in certain hypothetical proof-of-work protocols (see this) both when sorting or when using the modular multiplication combination, the one or two hashes used on top of the initial hash should be different (e.g. use a different initial constant).


OpenSSL - extract hash algorithm from signature data (PKCS#1 v 1.5) PKCS#1 v 1.5 stores hash algorithm identifier that was used to digest the original message. I would like to know if and how to extract this information.

I am working on a buffer containing the signature bytes and a buffer with public key.

I know it can be done (e.g. openssl rsautl does it with -verify and -asn1parse), but there is no sensible documentation for asn1 functions in openssl.

The hash identifier of a given RSASSA-PKCS1-v1_5 signature can only be obtained using the signature's public key¹. It's revealed by performing the signature verification steps 1 and 2/a/b/c (which basically gets the signature as an integer, raises it to the power $e$ modulo $N$ extracted from the public key, and converts back to bytes), then parsing the Encoded Message, which should be as per section 9.2 step 5, that is
$$\text{EM}=\mathtt{00}\mathbin\|\mathtt{01}\mathbin\|\mathtt{FF}\mathbin\|\ldots\|\mathtt{FF}\mathbin\|\mathtt{00}\mathbin\|T$$
where

the left two bytes $\mathtt{00}\mathbin\|\mathtt{01}$ are fixed, and followed by $f\ge8$ bytes at $\mathtt{FF}$ then a $\mathtt{00}$ ($f$ is maximal, that is for a $b$-bit public modulus $N$ the length of $T$ is $\left\lfloor(b-17)/8\right\rfloor-f$ bytes).
$T$ is ASN.1 DER encoded, containing the hash identifier and hash value.

The pragmatic approach to decode $T$ is to look at note 1 (or the table below, which comes from that).

MD2:         30 20 30 0C 06 08 2A 86 48 86 F7 0D 02 02 05 00 04 10 ∥ H
MD5:         30 20 30 0C 06 08 2A 86 48 86 F7 0D 02 05 05 00 04 10 ∥ H
SHA-1:       30 21 30 09 06 05 2B 0E 03 02 1A 05 00 04 14 ∥ H
SHA-224:     30 2D 30 0D 06 09 60 86 48 01 65 03 04 02 04 05 00 04 1C ∥ H
SHA-256:     30 31 30 0D 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 ∥ H
SHA-384:     30 41 30 0D 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30 ∥ H
SHA-512:     30 51 30 0D 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 ∥ H
SHA-512/224: 30 2D 30 0D 06 09 60 86 48 01 65 03 04 02 05 05 00 04 1C ∥ H
SHA-512/256: 30 31 30 0D 06 09 60 86 48 01 65 03 04 02 06 05 00 04 20 ∥ H

If we dive into the fine print, this is a DigestInfoValue. For example, the last entry decodes as

30 31   Sequence of 49 bytes

30 0D   Sequence of 13 bytes

06 09   OID of 9 bytes

60 86 48 01 65 03 04 02 06OID 2.16.840.1.101.3.4.2.6 meaning "SHA512-256 algorithm"

05 00   NULL for the Parameters field²

04 20   Octet string of 32 bytes

(the hash H follows as 32 bytes).

See this for how OIDs are encoded, and links to the ASN.1 DER specification. Examples can be thrown at Lapo Luchini's useful ASN.1 decoder.

¹  Given a signature, it's possible to make a new public/private key pair that makes this signature valid with any desired hash identifier and matching any desired known message (not only the the original) when checked with this new public key.

² This field must be present and NULL when encoding and checking $T$ in the context of RSASSA-PKCS1-v1_5. In other contexts a parser must accept that it is missing for the SHA algorithms, see the Exception in appendix B.1 and the two paragraphs above.


Chopping off SHA-256 entropy? I have a NoSQL key-value database. I want to insert couple million of records to it.

For the key generation, I'm, using a prefix (something like data-one-) and then concat the SHA-256 hash of something unique to the value stored. So the end key might look like

data-one-0000fdb60e164cf0bf07cef647354d26ed17c9492ca4bbf4114878325871fa1d

The problem is that the key is somewhat large and it will have impact of the DB performance. I want to chop off some of the hash to get a 64-bit string (so, 8 chars). So I'd chop the above key to

data-one-0000fdb6

But will it leave enough entropy for the remaining key? The DB will get large, and I don't want collisions, obviously. Will another hash be more suitable for this use, or is trimming SHA-256 fine?

Assuming the hash function is good, and SHA-256 is widely believed to be so, the probability of no collisions in $k$ samples into a range of size $n$ (e.g., obtained by selecting a subset of characters) is upper bounded by $exp(-k^2/2n).$

For you, say $k=2^{21}=2,097,152$ (couple million) and $n=2^{64}$ means that your probability of no collision is roughly

$$exp(-2^{42}/2^{65})=exp(-2^{-21})\approx 1-1.2\times 10^{-7}.$$

If you had 8 times more inputs (16 million plus) this would become

$$ exp(-2^{48}/2^{65})=exp(-2^{-17})\approx 1-7.6\times 10^{-6}$$

so probability of collision would be more than one in a million.


How does one design a traffic analysis resistant protocol? I'm curios about protocols which leak considerable personal information, like instant messaging exposing the contacts relation.  How does one make an instant messaging protocol which is resistant to traffic analysis?

I'm interested most specifically in server side attacks on users' contacts/friends lists.  In particular, the messaging system's servers are considered compromised, or even outright hostile.  I'm curious about the server aspect because Tor and I2P offer traffic analysis protection at the network level.

I could imagine an anonymous open mailbox like protocol.  A public key's hash identifies a public mailbox that's used for hello messages.  A hello message contains a seed for selecting a series of subsequent mailboxes that actually get used for communications.

You probably don't want attackers identifying the public mailboxes used for hello messages though.  You could perhaps scale the mailbox range with the user base to ensure that all mailboxes saw non-zero traffic while avoiding asking every participant to attempt to decrypt all messages as public key hello message.  Or maybe implement "please reuse" queue for mailboxes.

Is there any standard crypto literature on designing traffic analysis resistant protocols?

The obvious way to thwart traffic analysis is to send fixed-size messages at a fixed rate, whether there's any actual information to transmit or not.

I've heard it claimed that such protocols have been used in the past for diplomatic communications: a fixed-length packet of encrypted data would be sent say, once a day to an embassy in a foreign country, and the embassy would reply with another fixed-length encrypted packet.

Of course, such protocols are on one hand wasteful of bandwidth, and on the other constrain the peak bandwidth of the encrypted channel, which is why they're not more often deployed in practice.

To apply this principle to an instant messaging protocol, let's assume that we have a trusted central server acting as a message relay.  Each user of the messaging service establishes a separate encrypted connection to the server.  (We can use existing off-the-shelf protocols like SSL/TLS for that.)  Over these encrypted connections, the clients send messages to the server, which relays them to other clients.  (Again, we can use a standard instant messaging protocol like IRC or XMPP for the client–server interaction.)

The only unusual thing we'll do is throttle the communications between the clients and the server so that each client sends the server a single block of $n_c$ bytes at time intervals of $t_c$, and the server sends a block of $n_s$ bytes to each client at time intervals of $t_s$.  These blocks might combine multiple messages, and a single message might be split over multiple blocks; also, if there isn't enough data to fill a block, it's padded with dummy data which is ignored by the receiver.

(Note that the blocks need not map to single packets in the underlying transport protocol; it's enough that each block is fully assembled before it's passed to the transport layer, so that one cannot tell how many messages a block might contain by timing the transmission layer.  In many cases, this could be easily achieved by inserting an extra "chunking" layer between the messaging protocol and the encryption layer, without either having to be aware of the chunking.)

The parameters $n_c$, $n_s$, $t_c$ and $t_s$ should be chosen to match the needs of the messaging protocol.  For simple text-based instant messaging, $t_c$ and $t_s$ might be from 0.1 to 0.5 seconds, and $n_c$ and $n_s$ might range from, say, 64 to 256 bytes.  (Even lower bandwidth might be usable if the messaging protocol was optimized for it.)  Voice messaging is likely to need somewhat more bandwidth, depending on the audio quality desired.

The reason for using a central server is that, in a typical conversation, only one participant (or at most a few) is likely to be talking at any given time; thus, the peak bandwidth requirements for the clients will probably be more or less independent of the number of participants, whereas in a naive distributed protocol they'd scale linearly with it.  (This could be avoided by using more advanced messaging protocols, but that would complicate the example.)  Of course, the server would still require bandwidth proportional to the number of clients, but that's generally the case with centralized instant messaging protocols anyway, and it could be mitigated by connecting multiple servers in a network (with fixed-bandwidth links, of course!).


Proof of correctness of a homomorphic ElGamal sum Let's suppose we are using the exponential ElGamal as a public-key encryption scheme, so that we encrypt $g^m$ instead of $m$, for some generator $g$. Let $x$ be the private key, and $h=g^x$ be the public key.

We have two parties, and each one of them has a ciphertext encrypted with the same public key: $(R_1,S_1)=(g^{r_1}, g^{m_1} h^{r_1})$ and $(R_2,S_2)=(g^{r_2}, g^{m_2} h^{r_2})$, respectively.

These two parties then gather and perform the homomorphic sum of their ciphertexts by computing the product of their ciphertexts: $(R_3,S_3) = (R_1,S_1) \cdot (R_2, S_2) = (g^{r_1+r_2}, g^{m_1+m_2} h^{r_1+r_2})$.

Is there any way they can prove in zero-knowledge that the sum is correct? That is to say, that $(R_3,S_3)$ is the correct encryption of $m_1+m_2$ without revealing anything else about the addends ($m_1$ and $m_2$ should be kept secret) nor the (plaintext) value $m_1+m_2$?

The question is not very clear about exactly what you want to prove and what is publicly known, but here's my answer, based on my best guess at what you mean:

Each party should publish $(R_1,S_1)$ and $(R_2,S_2)$.  They should also publish $(R_3,S_3)$.
Now anyone can verify that $(R_3,S_3)$ is a correctly-formed encryption of the sum of the messages corresponding to $(R_1,S_1)$ and $(R_2,S_2)$.  In fact, there is no need for any fancy zero-knowledge proof: given $(R_1,S_1)$ and $(R_2,S_2)$, anyone who is interested can re-compute $(R_3,S_3)$ on their own and verify that the result they obtained matches what was published.


Proof that Alternating Step Generator and modifed ASG' have equivalent security? The Alternating Step Generator (ASG) is a PRNG combining 3 LFSRs. Output of the ASG is the XOR of the output of two clock-gated LFSRs. At each step, a single one of these LFSRs is clocked, according to the output of the control LFSR.

The best (AFAIK) claimed attack on the ASG is Reduced Complexity Attacks on the ASG (Slides). However it attacks a variant ASG', which output is the output of the clock-gated LFSR that was clocked.

Justification given in that paper is: It is known [13, 8, 12] that instead of working with the original definition of ASG we can consider a slightly different description (..).
[13] only states It is not hard to show that ASG and ASG’ are equivalent (..) with no argument. I fail to find a discussion about ASG' in [8]. [12] has a constructive proof, but I fail to get it (unless I assume that one of the LFSR is known/enumerated).

Any clue on a proof/sketch/argument that an attack on ASG' reconstructing the initial states of the LFSRs can be turned into an equally efficient attack on ASG?

Okay, I had a look at your source [12], e.g. ON EDIT DISTANCE ATTACK TO ALTERNATING STEP GENERATOR.

The original ASG defines the key stream Z = {z_i} from three shift registers X = {x_i}, Y = {y_i} and C = {c_i} via these steps:

  Initially, l = 0, t = 1.
  If ct = 1, then l = l + 1;
  Output z_t = x_l ⊕ y_(t−l) , where ⊕ is XOR operator;
  t = t + 1 and go to step 2.

E.g. we step one them depending on c_t, and use the latest output of both.

For the variant, we define w_i = z_i ⊕ z_(i-1), u_i = x_i ⊕ x_(i-1), v_i = y_i ⊕ y_(i-1), e.g simply the "difference sequences" of the original ones.

U = {u_i} and V = {v_i} can easily be created by LFSRs of the same length as these for X and Y, simply by adding or removing one feedback link. (And if we have the registers for U and V, we can get the registers for X and Y back.)

It now shows that we can derive W = {w_i} not only directly from Z, but also from U, V and C, using the modified construction:

  Initially l = 0, t = 1;
  If c_t = 1, then l = l + 1 and output w_t = u_l ;
  If c_t = 0, output w_t = v_(t−l).
  t = t + 1, go to step 2.

Why? Simply put the formulas:

If c_t = 1, then

w_t =      z_t        ⊕        z_(t-1)
    = (x_l ⊕ y_(t−l)) ⊕ (x_(l-1) ⊕ y_((t-1)−(l-1)))
    = (x_l ⊕ x_(l-1)) ⊕ (y_((t-1)−(l-1)) ⊕ y_(t−l))
    =      u_l        ⊕ (y_(t−l) ⊕ y_(t−l))
    =      u_l        ⊕         0
    =      u_l.

If c_t = 0, then

w_t =     z_t         ⊕     z_(t-1)
    = (x_l ⊕ y_(t−l)) ⊕ (x_l ⊕ y_((t-1)−l))
    = (x_l ⊕ x_l) ⊕ (y_(t−l) ⊕ y_((t-1)−l)
    =       0     ⊕ (y_(t−l) ⊕ y_((t-l)−1)
    =       0     ⊕      v_(t-l)
    =                    v_(t-l).

It is a bit confusing because of 1 and l looking quite similar here.

So, how would we do our attack on Z, given an attack on W?

Transform the observed sequence of Z into a sequence for W, by calculating differences of consecutive elements.
Break W, get formulas for C, U and V.
Transform the formulas for U and V back into these for X and Y by adding/removing
one feedback link.