In this example, which is a premaster secret, and which is a master secret? In the context of this data, as shown in the image below, which one is a pre-master-secret and which one is a master-secret. It looks to me as if the final value of 2, for Alice and Bob is a master-secret which can be then used for creating a symmetric key (AES). Am I right?

  Alice and Bob agree to use a prime number $p=23$ and base $g=5$.
  Alice chooses a secret integer $a=6$, then sends Bob $A=g^a\mod p$

  $A=5^6\mod 23$
  $A=15,625\mod 23$
  $A=8$

  Bob chooses a secret integer $b=15$, then sends Alice $B=g^b\mod p$

  $B=5^{15}\mod 23$
  $B=30,517,578,125\mod 23$
  $B=19$

  Alice computes $s=B^a\mod p$

  $s=19^6\mod 23$
  $s=47,045,881\mod 23$
  $s=2$

  Bob computes $s=A^b\mod p$

  $s=8^{15}\mod 23$
  $s=35,184,372,088,832\mod 23$
  $s=2$

  Alice and Bob now share a secret (the number $2$) because $6$ x $15$ is the same as $15$ x $6$.

The protocol outlined in the question is Diffie-Hellman key exchange with artificially small $p$. Beware that one thing is misleading in this exposition: for $p$ of practical interest, that is of some thousand(s) bits, when computing $g^a\bmod p$, one does not computes $g^a$ then reduce $\bmod p$ as shown, because $g^a$ is too huge. Instead, one reduces $\bmod p$ (at least) after each multiplication. Approximately ${3\over 2}\cdot\log_2a$ modular multiplications are performed in the simplest algorithm used in practice.

Thanks to poncho's comment, we know that the terms premaster secret and master secret are used in TLS, as:

  8.1. Computing the Master Secret

  For all key exchange methods, the same algorithm is used to convert
  the pre_master_secret into the master_secret.  The pre_master_secret
  should be deleted from memory once the master_secret has been
  computed.

  master_secret = PRF(pre_master_secret, "master secret",
                      ClientHello.random + ServerHello.random)
                      [0..47];

  The master secret is always exactly 48 bytes in length.  The length
  of the premaster secret will vary depending on key exchange method.

  8.1.1. RSA

  When RSA is used for server authentication and key exchange, a 48-
  byte pre_master_secret is generated by the client, encrypted under
  the server's public key, and sent to the server.  The server uses its
  private key to decrypt the pre_master_secret.  Both parties then
  convert the pre_master_secret into the master_secret, as specified
  above.

  8.1.2. Diffie-Hellman

  A conventional Diffie-Hellman computation is performed.  The
  negotiated key (Z) is used as the pre_master_secret, and is converted
  into the master_secret, as specified above.  Leading bytes of Z that
  contain all zero bits are stripped before it is used as the
  pre_master_secret.

  Note: Diffie-Hellman parameters are specified by the server and may
  be either ephemeral or contained within the server's certificate.

Thus, in the protocol of the question, which can be seen as a reduced example of Diffie-Hellman as it would be used in TLS, $s$ is the pre_master_secret; the master_secret would be derived from it.


Affine plaintext attack with GCD != 1 I'm trying to crack an affine cipher, but when cracking I cannot find the inverse of a number because the GCD is not 1. This is my plaintext and this is my ciphertext:

PLAIN:  072097 108108
CIPHER: 024328 164193

This is my function:

E(x) = ax + b (MOD 256256)

Gives:

E(072097) = 072097a + b (MOD 256256) = 024328
E(108108) = 108108a + b (MOD 256256) = 164193

So if we subtract these we get this:

139865 = 36012a (MOD 256256)
a = 139865 / 36012 (MOD 256256)
a = 139865 * 36012^-1 (MOD 256256)

Now GCD(256256, 36012) = 4. So there's no inverse because the GCD is not one.

I'm sure it's possible to crack this text but I just don't know how to do it because there's no inverse of 36012 and 256256.

Does anybody know how to crack this or get the inverse of 36012?

You seem to have made a mistake in your arithmetic: $$108108 - 72097 = 36011 \ne 36012.$$

The number $36011$ is invertible modulo $256256$, and thus you can find $a$ and $b$ in a straightforward manner.

More generally, you could end up in a situation where both the difference of the ciphertexts $d_c$ and the difference of the plaintexts $d_p$ might share the same common factor $g$ with the modulus $m$.  In that case, what you can do is divide both of the differences and the modulus by this common factor to obtain $d'_c = d_c / g$, $d'_p = d_p / g$ and $m' = m / g$, and solve the reduced recurrence $d'_c \equiv a d'_p \pmod{m'}$.  This will give you the value of $a$ modulo $m'$, which will correspond to $g$ different possible values of $a$ modulo $m$, differing by multiples of $m'$.  If $g$ is relatively small, this can be almost as good for most purposes as obtaining a unique solution, since e.g. to decrypt any additional ciphertext you can just try all the possible solutions and see which of the results makes the most sense.


If I know the salt, can I decrypt the commitment? Say, I salt my key(K) with y. So, my new Key is K' = Salt(K+y). Now, Alice sends commitment = E[K',M] to Bob. Bob knows the salt(y), but not K nor K'. Can Bob decrypt the message?

No, if Bob only knows the salt, he should not be able to decrypt the message.  This is based on the assumption that the key can't be derived from the salt or some combination of the cipher text and the salt.  If that is the case, the salt would not be enough to recover the key.


Is ssl_sign safe as it is using OPENSSL_PKCS1_PADDING I've been hearing a lot of scare talk about PKCS1 padding attacks.

Is PKCS1 v1.5 safe in signatures as it is practically transporting only message digest?

I'm using it in one of my applications so i'd like to know if it is safe to keep using it.

You're fine.

There are several different padding methods listed in PKCS v1.5.  The method that has active attacks is actually a padding used during public key encryption - that is, it's used to encode the plaintext message before handing it off to the RSA public function. We don't use that method to sign messages.

For that matter, the attack model used against that PKCS v1.5 encryption padding doesn't apply to a signature method.  In that attack model, the attacker  generates bogus ciphertexts, and send them to the holder of the private key and see what it does with them, and uses that to be able to figure out the decryption of a specific ciphertext.  This doesn't apply to signature methods, as the holder of the private key just signs messages, and performs any necessary padding itself.


Why do we need a digital signature? First of all, I want to say that I'm totally new to cryptography. I searched on crypto stackexchange but couldn't find the answer to the following question.(probably because it's easy, but I still don't get it)

My question is based on this question. So a signature basically does the following: message $\rightarrow$ hash $\rightarrow$ Bob's private key $\rightarrow$ combine signature with message $\rightarrow$ send to Alice $\rightarrow$ Alice decrypts the signature using Bob's public key $\rightarrow$ compares the hash of the signature with the text in the message:

Now the real question: Why not just encrypt the whole message with the private key of Bob send it to Alice and decrypt it with bobs public key? Because we can get Bob's public key from a CA and make sure we got the right public key, so if someone else sends the message we simply couldn't decrypt it.

I'm probably messing up some concepts so if something isn't clear, please leave a comment!

First an important point of terminology: the real question should be phrased "Why not just sign the whole message with the private key of Bob, send it to Alice, and verify it with Bob's public key?". Signature and encryption are very different things. We use "encryption" only when the goal is confidentiality; and encryption is performed with the public key of the receiver, rather than with the private key of the sender (as is the case for signature).

With that terminology issue set aside, what the question describes is the rough principle of signature with RSA, where the encryption operation can be carried with the private key instead of the public one. However that does not transpose to arbitrary asymmetric ciphers: their public and private key is often so different that there's no way to encrypt with the private key.

Further, there are security issues with what's proposed:

  if someone else sends the message we simply couldn't decrypt it.

Not true. If an attacker prepares the message as a legitimate sender but a different key, the message could be decipherable, only most likely into gibberish. So at least we need a procedure to recognize real messages from gibberish, and that's not easy (it might be impossible if what's signed was already encrypted, which is common practice).

Also, an attacker is not restricted to applying a proposed protocol with a different key. S/he can alter or combine existing cryptograms, and that opens to attacks. That's a reason why secure RSA encryption and secure RSA signature differ by more than an exchange of the role of keys.

We usually sign a hash of the message, rather than the message, primarily because the signature schemes that we use can only directly sign small amounts of data (in the order of tens to a few hundreds bytes). A hash reduces an arbitrarily large message to a small size (32 or 64 bytes are common), that we can sign in a single chunk. Signing the hash is as secure as signing the message, because (for a good hash algorithm) we do not know how to make two different messages with the same hash (collision resistance). Without this hash trick, we could still sign, but we'd need to break the message into numbered pieces, and sign each piece individually. Signatures tends to be several times larger than what they can directly sign, and at least one of signature generation or verification is typically compute-intensive; thus hashing saves bandwidth and improves performance except for very small messages.

For many signature schemes, there's another reason: hashing the message is necessary for security. Otherwise, some property of the signature scheme would allow forgery: perhaps some few messages would have a trivial signature, or the signature of a message could be derived from the signature(s) of some related message(s). With addition of the hash step, messages allowing such attacks can not be exhibited, because (for a good hash algorithm) we do not know how to make a message with a particular hash value (preimage resistance), or more generally with a special property.


In RSA, what's the risk of revealing $p^e\bmod N$? Assume a common RSA public key $(N,e)$ with $N$ the product of two unknown distinct randomly chosen large primes $p$ and $q$ of about the same size.

Does revealing $p^e\bmod N$ (in addition to the public key) allow factorization of $N$, or otherwise makes it markedly easier to solve the RSA problem? What about also revealing $q^e\bmod N$?

Does revealing $p^e\bmod N$ (in addition to the public key) allow factorization of $N$

Yes, with that extra information, $N$ is easy to factor.  A computation of $\gcd( N, p^e \bmod N )$ gives the factor $p$ (because $p$ is the only prime the two integers $N$ and $p^e \bmod N$ have in common, it is a factor of both integers, while $q$ is not a factor of $p^e \bmod N$)


Is there a maximum number of encryptions I should make with the same RSA key? From an answer to the question RSA maximum bytes to encrypt, comparison to AES in terms of security? I learned that there is a theoretical limit of how much data can be safely encrypted with symmetric block ciphers (like AES for example) with the same key. The answer says that for a block size of n bits there are theoretical concerns when approaching 2^(n/2) encrypted blocks with the same key, and a comment suggests to use 2^(n/4) for a more defensive approach. For AES with its 16 bytes per block, both figures would be significantly more than any single AES key would ever encrypt in my application, so I needn't worry about that.

Nevertheless, even if this limitation bears no practical relevance for me and I have not understood why it exists, I still consider it "good to know" (e. g. because for other symmetric block ciphers with smaller block sizes, it might become relevant).

Hence I'm wondering: are there a similar hypothetical limitations for RSA? In other words: is there some kind of "maximum number of encryptions" I should do with the same RSA key, or is it truly infinite how many times I can encrypt something (in my case: varying 128-bit AES keys) with RSA (assuming the private key remains private forever and there's no attack found)?

Notes:

I haven't yet found anything about it, mainly because when something like this is asked, the answers tend to immediately focus on how much data can you encrypt at once, but they don't say anything about the maximum number of encryptions.

And finally, for completion's sake: I'll use RSA-2048+OAEP-SHA256, but the question is targeted towards RSA in general, for any padding algorithm, and if the answer varies by padding algorithm used, that'd be nice to know.

Is there a maximum number of encryptions I should make with the same RSA key?

No, at least, none that can be practically performed.

For RSA, we assume that the adversary has the public key, and hence is able to generate his own plaintext/ciphertext pairs, and in fact, can do that a huge number of times, should he find that helpful.

Hence, if RSA becomes insecure if you encrypt, say, $2^{80}$ messages, then a large adversary can go ahead and encrypt that many messages himself (and thus obtain whatever weakness that was posited.

The fact that we believe that, say, 3k RSA cannot be broken with less than $O(2^{128})$ operations would therefore say that it's safe to encrypt $2^{128}$ messages (and you'll never ever need to encrypt that many).


What exactly is "Plausible Deniability in Internet Protocols"? I am trying to understand the meaning of "Plausible Deniability Feature of Internet Protocols". To be specific, I am not able to understand what "Plausible Deniability" exactly means.

Could someone explain what these terms mean and give some examples?

The Latin word plausibilis means "deserving applause, acceptable", and this morphed into our English word plausible with the meaning, "having the appearance of truth", first used around 1560.

Merriam-Webster defines plausible as:

superficially fair, reasonable, or valuable but often specious
superficially pleasing or persuasive
appearing worthy of belief

"Plausible deniability" is often used in intelligence work: in false flag operations, active measures, offensive cyber ops, anti-terrorism in denied countries--we did not do it, and my boss especially does not know anything about it.

In cryptography it can mean deception about the presence of a message--while having a reasonable explanation. Alice can deceive you about a chunk of data, and you will not know for sure whether plaintext is or is not there--it will take work to figure out the truth, but even after you prove that Alice deceived you, she can still make a case that is believable... or say  I did not know....

"Plausible deniability" can also apply to hiding an encrypted volume in a storage device and then denying its existence.  Veracrypt is a good example of a product that can offer plausible deniability:  this USB does not contain a hidden, highly encrypted volume, enciphered with a cascade of TWOFISH/AES256 hashed with Whirlpool.

With internet protocols it means that two parties can deny having taken part in key exchange.  This might seem to be an odd virtue in key exchange.  In fact, this kind of deniability is an important feature.

You can read more about this last topic here.


Is digest=HASH(HASH(a)+HASH(b)) equivalent to publishing two digests? Is combining digests (created using a hash function) using arithmetic addition, and then hashing and publishing the result, less secure than publishing the set of digests?

Does the answer change if the outer hash function is different from the inner function?

I am working on a proposal for Bitcoin to enable m-of-n signatures for transactions, and am considering using a 160-bit digest of the public keys computed as:

digest = RIPEMD160(SUM(SHA256(public_key_n)))

The number of public keys involved will typically be less than ten, and will never be more than 20.  The order of public keys is irrelevant, I am just concerned with an attacker finding another set of public keys that hash to the same digest.

If I get the suggested construction correctly, it is to

1) hash n values (with SHA-256);

2) add theses hashes, perhaps mod 2256;

3) hash the sum (with RIPEMD-160).

This would be potentially unsafe: creating a collision or even second pre-image at step 2) reduces to a knapsack problem, and this has a poor safety record; it might be workable when the number n of inputs allowed gets above some threshold, with some relation to the number of bits in the first hash.

There is a simple, safe solution: at step 2), instead of adding the hashes, sort them, then concatenate them; sorting keeps the associativity and commutativity of addition (and is otherwise unnecessary). The construction becomes essentially as resistant as the weakest of the hash functions against collision (second pre-image resistance is the weakest of that for the first hash function for n preimages, and the second hash function).

Note: I see no good reason to use two different hash functions.

-

Here is an attack against a slight modification of the proposed construct, with addition replaced by XOR. It is a second-preimage attack: the attacker has a set of valid input values, and wants another set with the same overall hash after step 3).

In a preparatory step, she generates random values (all distinct from each others and valid input values), hashes them with the first hash, until a basis of 256 hashes emerges from the accumulating hashes; that is, until each of the values 20, 21, .. 2255 can be expressed as a linear combination of XOR of some of the 256 hashes in that basis. This is simply a matter of adding the newly generated hash to the basis, unless it turns out to be a linear combination of the ones already in the basis, which can be checked by Gaussian elimination. The basis is complete when it contains 256 hashes, which will happen shortly after the 256th random value.

To obtain a forgery, she performs steps 1) and 2) normally with the valid input strings. She expresses the result as a linear combinations of the hashes in her precomputed basis, again by Gaussian elimination. It will consist of the XOR of about 128 hashes from the basis. The random strings that generated these hashes form a set which is a forgery. Step 3) is not necessary. It is easy to markedly reduce the number of strings in the forgery.

If addition modulo 2256 is used, or worse with straight addition, things are markedly more difficult, but conceivably still manageable (with more vectors in the forgery, and in the case of straight addition more vectors in the original); it is a knapsack problem, with a nearly unlimited supply of values.

-

I do not know how safe the system is with the number of elements limited to 20 (which I now realize is part of the statement); but at any rate, the addition step potentially is a weak spot.


Performance for Subbytes in AES I´m implementing the AES-encrypt algorithm for the SSE2 instruction set.

For the Subbyte function i use movzx, having loaded the S-box in the cache of the CPU for more performance. That cost about 56 OPS wing CPU.

I was wondering if you could calculate the value of the bytes without having to change the vector so seriously?
In particular, I would like to ask if you can significantly improve on a round of AES-128-Encryption taking about 108 OPS?

Fast software implementations of AES were proposed in a number of research papers. The state-of-the-art approach is to do a bitsliced implementation, where bits of sequential blocks at identical positions are processed at the same time.

The fastest implementation described so far that does not use AES-NI instructions was designed by Kasper and Schwabe. Their paper is online and is highly recommended for those who are interested in fast AES implementations. It would not make sense to copy the entire paper here, but specific questions can be answered.


Why does the Gameboy Advance serial encryption include the destination byte address? The Gameboy Advance encrypts data sent over its serial port. It assembles a random number to seed a linear congruential generator. Then, it xors this PRN, the data, a symmetric key, and the byte offset from the file.

Is there a rationale for this? The receiver must know the byte address, because it needed to know how many times to iterate the LCG.

(See here for a description of the algorithm.)

I'm trying to determine whether the algorithm is a stream cipher or some version of a block cipher in CTR mode.

Quoting the linked source:

 if normal_mode    then c=C387h:x=C37Bh:k=43202F2Fh
 if multiplay_mode then c=FFF8h:x=A517h:k=6465646Fh
 m=dword(pp,cc,cc,cc):f=dword(hh,rr,rr,rr)
 for ptr=000000C0h to (file_size-4) step 4
   c=c xor data[ptr]:for i=1 to 32:c=c shr 1:if carry then c=c xor x:next
   m=(6F646573h*m)+1
   send_32_or_2x16 (data[ptr] xor (-2000000h-ptr) xor m xor k)
 next
c=c xor f:for i=1 to 32:c=c shr 1:if carry then c=c xor x:next
wait_all_units_ready_for_checksum:send_32_or_1x16 (c)

 pp    palette_data
 cc    random client_data[1..3] from slave 1-3, FFh if slave not exists
 hh    handshake_data, 11h+client_data[1]+client_data[2]+client_data[3]

I read the question as asking the role of xor (-2000000h-ptr).

It ads a small layer of security by obscurity, but does not strengthen the algorithm from a cryptographic standpoint, since a passive eavesdropper can know ptr by merely counting the octets exchanged.

The algorithm is a stream cipher for encryption (with the keystream obtained as the XOR of a Linear Congruential Generator m, the aforementioned (-2000000h-ptr), and key k); and a MAC for integrity (using a Cyclic Redundancy Check c with feedback polynomial defined by x). The whole thing is more security by obscurity than real crypto.

Update: The ptr term can not be naturally considered as the counter of the CTR mode of operation. For this we would need chunks of the keystream to be expressable as a function of key and counter, without other internal state evolving sequentially. Here we have other such internal state m. Otherwise said, it is easy to convert a cipher operating in CTR mode for direct access, when here the iterated LCG makes that uneasy. I see no natural way to consider this as a block cipher in any mode.

On the other hand, if we really wanted that, it is possible to express the state of the LCG m as a function F of the current value of ptr and the initial m0=dword(pp,cc,cc,cc), and then the keystream becomes (-2000000h-ptr) xor F(ptr,m0) xor k, or $E_{(\mathtt{m_0},\mathtt{k})}(\mathtt{ptr})$, and we have a CTR mode with a block cipher $E$, having extremely weak diffusion of its plaintext input. That would be grossly inefficient if we implemented F iteratively, but there are ways around.


How the degree reduction in BGW protocol works? In the BGW protocol given in the original paper http://groups.csail.mit.edu/cis/pubs/shafi/1988-stoc.pdf

It says the after the randomization step every party $P_i$ finds its share $s_i = \tilde{h}(\alpha_i)$ on the polynomial $\tilde{h}(x) = h(x)+\sum^{n-1}_{j=0}q_j(x)$, and then it applies degree reduction on $\tilde{h}(x)$.

It defines vector $S = [s_0 s_1 \cdots s_{n-1}]$ and a constant matrix $A_{n\times n}$, such that $R = S.A$. where $R$ is the vector of shares of each party $P_i$ on polynomial $k(x)$ which is $t$-degree and $k(0) = \tilde{h}(0)=a.b$.

So, what is want to know that how this matrix multiplication is evaluated among the parties t-privately ? Because each party holds $s_i$ not known to any other party. How the whole $\mbox{truncate}(\tilde{h})$ is done ?

I refer you to a full proof of the paper with all of the details on how the protocol works. See: http://eprint.iacr.org/2011/136.pdf.


Constant Time Multiplication for Cryptography in Pure Software without Hardware Multiplier or Barrel Shifter To prevent various forms of timing side-channel attacks, it's strongly advisable to implementing public-key cryptography in constant time. Or at least, without secret-dependent timing variations. However, as far as I'm aware, such implementations rely on a constant-cycle hardware multiplier. Sometimes it's also possible to replace some multiplications with shifts and adds, still, a constant-time implementation requires a barrel shifter.
Hypothetically, if I want to implement public-key cryptography (either elliptic curve or discrete log) on the cheapest microcontrollers without either a hardware multiplier or barrel shifter, what are my options for a constant-time multiplication algorithm in pure software? Constant-time multiplication in pure software sounds like a basic enough problem and many researchers must already have investigated it, but I don't know where to look. What algorithms are available, and how do they perform comparing to their non-constant time counterpart? 10x slower? 100x slower?
An obvious solution I can imagine is using a 16-bit lookup table for 8x8 multiplication, then pretending that we have a 8-bit multiplier and proceeding from here. On an embedded system without cache, on ROM, there will be no timing variation. But are there any alternative approaches (or a variation of the LUT approach that performs better in time/space)?
To clarify my motivation, I know this is impractical in real applications (even if one is stubborn enough to do it, a crypto coprocessor would be the solution), I ask it mostly due to theoretical interests.

Constant-time multiplication in software without constant-time multiplier is easy. In C, this working code to compute $x\cdot y$ for 8-bit inputs is typically¹ constant-time:
unsigned mul(unsigned char x, unsigned char y) {
  unsigned r = x, s = x&-(y&1);
  s += (r += r)&-((y >>= 1)&1);
  s += (r += r)&-((y >>= 1)&1);
  s += (r += r)&-((y >>= 1)&1);
  s += (r += r)&-((y >>= 1)&1);
  s += (r += r)&-((y >>= 1)&1);
  s += (r += r)&-((y >>= 1)&1);
  return ((r+r)&-(y>>1))+s;
}

On a $b$-bit CPU, it is required $O(b)$ instructions, compared to $O(1)$ with a constant-time $b$-bit multiplier. Assembly often makes it possible to do considerably better than the obvious translation of the above code, especially on architectures without built-in 16-bit addition.
It's possible to compute $(x\,y)+z$ where $0\le z<2^b-1$ by the same method. This can be used to perform multiplication of arbitrarily large fixed-size quantities in constant time using the schoolbook algorithm, or others such a Karatsuba, translated to base $2^b$ rather than base $10$, with essentially the same $O(b)$ performance penalty compared to implementation with a constant-time multiplier.
The most serious difficulty is the same as on architectures with a constant-time multiplier: constant-time modular reduction.
I don't get how the lack of barrel shifter is an issue: in the arithmetic used in ECC cryptography, there's typically no computed shift involved, thus no opportunity that the lack of barrel shifter degenerates into a timing dependency. And the natural form of most algorithms uses shifts by one, thus a barrel shifter would not help much anyway.

One thing worth investigation on CPUs without hardware multiplier is Elliptic Curves over $GF(2^m)$, e.g. sect239k1. I know no reason this would be much less secure than secp224k1, and scalar multiplication no longer uses any integer multiplication, so the lack of hardware multiplier has low penalty.

¹ Except if the compiler introduces branches or if some of the instructions involved are not constant-time, but I've ever experienced that.


ECDH for more than two parties With classic diffie-hellman it's possible do it with more than two parties. Is this applicable to elliptic curve diffie hellman?

I'm guessing not.

With ECDH you have a scalar number as the private key and an x, y coordinate (or just x coordinate in the case of Curve25519) as the public key. You multiply the coordinate by the scalar and you get a new coordinate. The x coordinate of that is the shared secret.

If you had two public keys and one private / public ECDH key pair...  if you didn't discard the y coordinate you could multiply one of the public key coordinates by the private key but then it's not clear what you would do with the other public key coordinate. Maybe there's nothing you can really do to facilitate ECDH for more than two parties?

You can do ECDH with more than two parties. See the below adaptation of the wikipedia example for an EC group -

The parties agree on the algorithm parameters, a curve over $E(\mathbb{F}_p)$ and base point $G$.
The parties generate their private keys, named $a$, $b$, and $c$ (these are integers).
Alice computes $aG$ and sends it to Bob.
Bob computes $(aG)b = (ab)G$ and sends it to Carol.
Carol computes $(abG)c = (abc)G$ and uses the x coordinate as her secret.
Bob computes $bG$ and sends it to Carol.
Carol computes $(bG)c = (bc)G$ and sends it to Alice.
Alice computes $(bcG)a = (bca)G = (abc)G$ and uses the x coordinate as her secret.
Carol computes $cG$ and sends it to Alice.
Alice computes $(cG)a = (ca)G$ and sends it to Bob.
Bob computes $(caG)b = (cab)G = (abc)G$ and uses the x coordinate as his secret.

A note about your concern with Montgomery curves (such as curve25519). Montgomery curves indeed only return the x coordinate but point multiplication only requires the x coordinate as input. Said another way, the Montgomery ladder which is used for point multiplication does not use the y coordinate in the algorithm. So the doing e.g. $(aG)b$ is fine since $aG$ will return an x coordinate, and we can use the Montgomery ladder to multiply that by $b$.

In fact, multi party DH will work for any group that has a "combine" and a "scale" operations for its elements.


For which RSA moduli, precisely, is $e=d$ for all $e$? This question shows that there are at least two valid RSA moduli $n$, namely $35$ and $91$, such that for any $e$ coprime to $\lambda(n)$, $$e^2\equiv1\mod\lambda(n)\text.$$
Reading the linked question, I wondered if there is a "simple" description of the set of numbers $n$ that have this property. In particular, are there infinitely many such numbers?

I wondered if there is a "simple" description of the set of numbers n that have this property.

Yes, there is; $n$ has a prime factorization $p_1 \cdot p_2 \cdot ... \cdot p_n$ such that all the primes are unique (i.e. $n$ is square-free), and for each prime factor $p_i$, $p_i-1$ must be a divisor of 24.  In other words, each prime must be a member of the set $\{2, 3, 5, 7, 13\}$

Why is this?  Well, $e^2 \equiv 1 \mod \lambda(n)$ (for $e$ r.p. to $\lambda(n)$) is equivalent to $e^2 \equiv 1 \mod p_i-1 $ for all $i$ (for $e$ r.p. to $p_i-1$); this latter holds only if $p_i-1$ is a divisor of 24.

As a consequence, we see that there is only a finite number of such modulii; if we restrict ourselves to modulii with two factors, we see that 91 is the largest possible.  If we include multiprimes, then the largest possible is $2730 = 2 \times 3 \times 5 \times 7 \times 13$


What's the algorithm behind MySQL's sha256_password hashing scheme? MySQL's old mysql_native_password hashing scheme was the equivalent of this in PHP:

sha1(sha1('password', true));

That's a hex-encoded SHA-1 hash of a binary SHA-1 hash of the password, without any salting.

MySQL 8.0 introduced a two variants of a new hashing scheme based on SHA256 called caching_sha2_password and sha256_password, the former being the default (docs). Despite their name, neither appears to be vanilla SHA256.

(Yes, I know SHA256 is not a great choice for password hashing, but it's a lot better than SHA-1 and it wasn't up to me!)

Here's an example. I created a hash for the password password, and it created a mysql.users password hash like this:

$A$005$wU"H/k5|5;f!kP_&N4cvqu6bppuYjCvqhg2blU.NcJHkkhaVj.QNt7pipg4p3

I'm guessing that (separating by $ chars), A means it's SHA256 (the scheme may support other SHA2 variants in future), and that the 005 is a salt, but the rest of the string isn't a common format - it doesn't look like either regular hex output or base64, nor is it raw binary.

Can anyone tell me the actual algorithms for these new schemes, in PHP or similar code?

Update

Thanks to @kelalaka for some important pointers, I had a crack at writing this in PHP:

$originalhash = 'wU"H/k5|5;f!kP_&N4cvqu6bppuYjCvqhg2blU.NcJHkkhaVj.QNt7pipg4p3';
$binaryhash = base64_decode($originalhash);
$salt_length = 20;
$hash_length = 43;
$rawsalt = substr($binaryhash, 0, $salt_length);
$rawhash = substr($binaryhash, $salt_length);

$password = 'password';
$iterations = 5;
$iteration_multiplier = 1000;
$it = $iterations * $iteration_multiplier;
$hash = $rawsalt . $password;
for ($i = 0; $i < $it; $i++) {
    $hash = substr(hash('sha256', $hash, true), 0, $hash_length);
}
$hashoutput = base64_encode($rawsalt . $hash);
var_dump($originalhash, $hashoutput);

However, this doesn't produce matching output:

string(61) "wU"H/k5|5;f!kP_&N4cvqu6bppuYjCvqhg2blU.NcJHkkhaVj.QNt7pipg4p3"
string(72) "wUH/k55fkPN4cvqu6bppuYjCvqgx75cg5UeVzAVpx0OzU7KS2Klujh3rbHzrAena3/MBAA=="

It's too long
I suspect the encoding scheme is not base64; notice the salt diverges from the original even though it is unchanged.
I'm not sure whether the starting string should be salt + password or password + salt.
I'm not clear when the truncation of the binary hash should be performed - in the loop, or after?

According to the MySQL Server Blog, it is:

  The advantage of mysql_native_password is that it support challenge-response mechanism which is very quick and does not require encrypted connection. However, mysql_native_password relies on SHA1 algorithm and NIST has suggested to stop using it.

  caching_sha2_password tries to combine the best of both worlds.

XOR( SHA256(pwd),SHA256(SHA256SHA256(pwd)) , Nonce)

  \$A\$005\$wU"H/k5|5;f!kP_&N4cvqu6bppuYjCvqhg2blU.NcJHkkhaVj.QNt7pipg4p3

From the source code sha2_password.cc

  Expected format

  DELIMITER[digest_type]DELIMITER[iterations]DELIMITER[salt][digest]

Where the delimiter is $

  digest_type:

  A => SHA256

  iterations:

  005 => 5*ITERATION_MULTIPLIER

  salt:

  Random string. Length SALT_LENGTH

  digest:

  SHA2 digest. Length STORED_SHA256_DIGEST_LENGTH

From file i_sha2_password.h

  #define CRYPT_SALT_LENGTH 20

  const unsigned int STORED_SHA256_DIGEST_LENGTH = 43;


Does an encrypted random sequence conserve its "randomness"? If you have a random uniform sequence of bits $A$ generated by a TRNG with good performance of randomness tests (eg Dieharder, NIST, Kolmogorov complexity, chi-square, etc) and perform an encryption (eg AES) with a known deterministic key $B$ so that it results in a new encrypted sequence $C$.

Is the encrypted sequence $C$ generated by a TRNG? Should it have the same good performance in the randomness tests as the unencrypted sequence $A$?

Yes. If $r\colon\;\Omega\to X$ is a uniformly distributed random variable, and $f\colon\;X\to Y$ is a bijective function (such as, for instance, a symmetric cipher instantiated with some key), then $f(r)\colon\;\Omega\to Y$ is uniformly distributed as well.

The proof is simple: For all $y\in Y$, we have
$$\Pr[f(r)=y] = \Pr[r=f^{-1}(y)] \text,$$
and the latter probability is independent of the choice of $y$ since $f$ is a bijection and $r$ is uniformly distributed. Hence $f(r)$ is.


POW with Linear time to solve it? Any suggestions for A Proof-of-Work algorithm in literature so that the time required for solving it is linear with the puzzle difficulty ??

I don't think an algorithm like that would exist. For PoW to facilitate a random slot leader for block generation, it has to be necessary that the PoW puzzle is really hard to solve by anyone and that no deterministic polynomial time algorithms exist which promise a solution to that puzzle, because if they would then I think that a person with a faster rig and a faster processor would solve the PoW puzzle the fastest and become the slot leader every time.
Since I have already stated that there shouldn't exist any deterministic algorithm to solve the puzzle in polynomial time, this means that the best that anyone contending for becoming the slot leader can do is to try the probabilistic approach and wish that their random nonce solves the puzzle faster than anyone else. It is just because of this randomized (probabilistic) nature of the solution to the puzzle that the very slot leader elected is random in nature.
If you know about complexity classes of P and NP, then you will realize that if PoW is linearly solvable then it lies in P, whereas it should lie in NP i.e. given an oracle which takes all the correct steps and makes all the correct choices (meaning that selects the random nonce correctly every time) every time, then the problem is polynomial time. This means that given a solution, you can verify that the nonce is correct in polynomial time but you cannot solve the puzzle in polynomial time.


Proving/verifying keys for zero knowledge proof (zkSNARK) in a simple case (possession of a string whose hash is x) I'm studying simple examples to understand how ZK-Snarks work.

Following this great introduction, I'm trying to elaborate a generator function giving a prover and verifier keys:

pk, vk = G (C, lambda)

that would work on the simple case

C (x, w) { return (sha256 (w) == x); }

i.e. how to build a zero knowledge proof scheme for the simple use case:

I know a string s whose hash is x. I can prove it to you, without revealing s.

How to actually build a zk proof algorithm for this simple use case? (following the article's notations, how to get proving/verifying keys and functions, given a lambda "waste" that will be discarded after generation?)

This section from the paper Succinct Non-Interactive Zero Knowledge
for a von Neumann Architecture is what you want. See the following image.

I will describe the very high-level idea below.
ZKSNARK that libsnark and ZCash use is based on the Knowledge of Exponent assumption. Basically, the exponent used in the elliptic curve cryptography is just the "toxic waste" that you mentioned. Denote $G$ as the group generator of the curve used, $G*t, G*t^2, \ldots$ ($t$ is part of the so-called private coin and this series will continue until the evaluation of some polynomial like $H(t))$ is covered. You may wonder what $H(t)$ is. A brief answer is that we have transformed the NP statement (the preimage of SHA256 is a witness to the NP statement due to the property of the one-way function) to the arithmetic circuit consisting of additive and multiplicative gates (just assume no boolean comparison here), then to the polynomial $A(t)*B(t)-C(t)=H(t)*Z(t)$. This polynomial equation holds ($H(t)$ exists particularly) $iff$ the proving procedures are correctly executed. Put it more simply, if the circuit contains $N$ gates (constraints), then we need a polynomial representation of order $N$. Again why this weird equation? Assume the underlying computation takes $T$ steps, this gives us lower bound $T\log(T)$ on proving time thanks to the deep connection between polynomials and the $\text{Fast Fourier Transformation (FFT)}$. Before this method, the proving time is at least $T^2$ (inner product and outer product are used, thus the square). On the other hand, we can further reduce the polynomial equation to the $\text{ECC}$ bilinear pairing problem. We need this one last transformation because it allows the verification steps to be very efficient. The proof is constantly 128 bytes (3 pairings) and the verification is always around 3-5 ms. So now we can also answer where this "trusted setup" concept comes from. It is import no one has a trapdoor to the setup procedures, i.e., no one has access to the "toxic waste". Typically, multi-party computation is applied so that if at least one party is honest, the setup is a trusted one. Another thing you mentioned is $pk$ and $vk$. As you can see, $pk$ is a proving template that uses homomorphic encryption for the verifier to check the knowledge commitments of polynomials $A(x)$, $B(x)$ and $C(x)$ and whether they use the same coefficients. And $vk$ is just used in the pairing.

If you want to know more details, a great start would be the explanation by Vitalik Buterin. It is not hard to understand this one. Here is another somehow more formal explanation by Christian Reitwießner. Also, for more academic teaching resources, this lecture series covers the general topic of verifiable computation, interactive arguments system, ZKSNARK with pre-preprocessing, ZK system front-end transformation and much more.


Storing salts and iteration number? I have a function that derives two sub-keys from one passphrase using PBKDF2 one which is used as a encryption key the other for HMAC generation, because these two sub-keys will need to be regenerated when the user wishes to decrypt there file so the salt used and the number of iterations must be available to the client and I am wondering whether it would be a massive security risk to simply store them in the cipher text or somewhere on the users machine?

The reason we add salts to the key derivation process it to make the key hash image unique for a given password. Actually a salt is added to remove weakness when an attacker has a list of "most common password". Adding a salt make the attacker job harder, he has to rebuild the attack per every salt he finds, i.e.: per every ciphertext he gets. It is considered safe to store the salt with the cipher text.

Similarly the iteration number is there to slow down a brute force attack, so it is still safe to store it with the cipher text.


When is a cryptosystem or its algorithm (like RSA) considered efficient? When is a cryptosystem (like RSA) or its algorithm for keygeneration, encryption and decryption of messages considered efficient? Is there some bound in complexity which splits both efficient and not efficient cryptosystems or algorithms of cryptosystems?

From a theoretical perspective in cryptography, a cryptosystem is efficient when the execution time of the algorithm run by the legitimate user grows as a polynomial of a security parameter $k$, while the execution time for the best algorithm an adversary can run to break the system grows faster than any polynomial of $k$ (some change that to: exponentially with $k$, thus giving a different, less common definition).

This definition does not require to specify what $k$ is, and it's readily proven that changing $k$ to a polynomial in $k$ does not change the outcome of the above test. But often, $k$ is the size of something in bit, like the key, or the signature. In symmetric crypto, it is typically the size of the secret key.

From a practical perspective, the line is not clear. Make it: whatever is acceptable in the context.


XOR of 16-bytes variables gives a result of size not equal to 16 I'm trying to write a XOR code for implementing CBC mode of operation from scratch but i seem to have some problem.The function takes two byte variables of 16bytes and the expected output should be 16bytes which we get it from the first line in main but when that string is converted to bytes the size increases. Feels like I'm misunderstanding something

from binascii import unhexlify
import os

def xor(string1,string2):
    list1=[]
    for i in range(len(string1)):
        list1.append(chr(string1[i]^string2[i]))
    return (("".join(list1)))

if __name__ == "__main__":
    print(len((xor(os.urandom(16),os.urandom(16))))) #always comes out 16 #type string
    print(len((xor(os.urandom(16),os.urandom(16))).encode("utf-8"))) #never equal to 16 #type byte

In implementing crypto, it is essential to distinguish strings (of characters) from byte vectors, also known as bytestrings or byte arrays.

In most computer languages, strings store characters, not bytes, and are not adequate for (un-encoded) intermediary values, ciphertext, keys, Initialization Vectors.. even when and if adequate for plaintext. In C, characters can be signed, and 0 ends a string. In Java, strings contain 2-byte characters. In many modern languages, strings contain abstract Unicode points, or a subset of that, or their representation as bytes per UTF-8 (1 to 4 bytes per character).

The first computational step of encryption of a string is to convert it to byte vector. In modern Python practice, that can be

myString = 'Per Pythagoras: x²+y²=z²'
myByteVector = bytes(myString, 'utf-8')

which here turns a 24-character string into a 27-byte vector. It happens that with UTF-8 encoding, what an American considers a normal character takes one byte, except when it doesn’t (that’s two examples since the previous comma!).

Then byte vectors can be processed, XORed.. (typically, much more naturally than strings) and won't change length unexpectedly.

On decryption, the byte result needs to be changed back¹ to characters, perhaps as a string. In modern Python, the idiom can be

myString = str(myByteVector, 'utf-8')  # can cause exception!

Note: when and if a ciphertext, key, Initialization Vector.. needs to be represented as string, it should be encoded per some binary-to-text encoding, such as the popular Base64.

¹ Beware that's not always possible, e.g. when the ciphertext was altered or the deciphering key is wrong. In such case, the best outcome is an exception; others include garbage text, a beep when that's displayed, a devastating security vulnerability, execution of the HCF instruction, torn out paper on a  Teletype.


Can we use a hash-based stream cipher against DPA attacks? There have been lots of DPA researches against block ciphers.

I was wondering if we use a cryptographically secure hash of an incremental counter as a stream cipher, will it withstand DPA attacks?

Ciphertext = Plaintext ⊕ HASH(counter)

My assumptions are:

The initial value of the counter is kept secret;
There seems to be not many effective DPA attacks against SHA (not HMAC).

There seems to be not many effective DPA attacks against SHA

How do you come to that conclusion?  Is it because there aren't many published results of using DPA attacks against SHA?  Well, that's mostly because SHA is most often used to hash publicly available data, and so there's less of a point using a DPA attack to recover that data.

Now, any side channel attack (such as DPA) is actually an attack against the implementation, not against the base crypto.  Of course, if we consider DPA attacks against SHA implementations, we need to consider "how difficult is it to make a SHA implementation that is strong against DPA attacks?"

Well, there's nothing in the SHA architecture (either SHA-1, SHA-2 or SHA-3) that makes it specifically easy to provide such protection.  Now, you could create such an implementation (using, say, thresholding to disguise the individual bits); however that's likely to be significantly slower than a standard implementation.


What encryption should I use: Blowfish, Twofish, or Threefish? The title of this thread pretty much sums up what I'm asking: what is the best encryption to use out of the three — Blowfish, Twofish, or Threefish?

TL;DR: Twofish and Threefish are fine.
It is not the best idea to have the cipher you want to use hardcoded because you can't upgrade easily when one of them is broken. to quote mikeazo in the comments:

What you should do is develop your application to not be bound to a specific cipher.

Twofish

In 1999, Niels Ferguson published an impossible differential attack that breaks six rounds out of 16 of the 256-bit key version using $2^{256}$ steps.

As of 2000, the best published cryptanalysis on the Twofish block cipher is a truncated differential cryptanalysis of the full 16-round version. The paper claims that the probability of truncated differentials is $2^{−57.3}$ per block and that it will take roughly $2^{51}$ chosen plaintexts (32 petabytes worth of data) to find a good pair of truncated differentials.

Bruce Schneier responds in a 2005 blog entry that this paper does not present a full cryptanalytic attack, but only some hypothesized differential characteristics: "But even from a theoretical perspective, Twofish isn't even remotely broken. There have been no extensions to these results since they were published in 2000."

https://www.schneier.com/academic/twofish/
https://www.schneier.com/blog/archives/2005/11/twofish_cryptan.html
Threefish

In October 2010, an attack that combines rotational cryptanalysis with the rebound attack was published. The attack mounts a known-key distinguisher against 53 of 72 rounds in Threefish-256, and 57 of 72 rounds in Threefish-512. It also affects the Skein hash function. This is a follow-up to the earlier attack published in February, which breaks 39 and 42 rounds respectively. In response to this attack, the Skein team tweaked the rotation constants used in Threefish and thereby the key schedule constants for round 3 of the NIST hash function competition.

In 2009, a related key boomerang attack against a reduced round Threefish version was published. For the 32-round version, the time complexity is $2^{226}$ and the memory complexity is $2^{12}$ for the 33-round version, the time complexity is $2^{352.17}$ with a negligible memory usage. The attacks also work against the tweaked version of Threefish: for the 32-round version, the time complexity is $2^{222}$ and the memory complexity is $2^{12}$ for the 33-round version, the time complexity is $2^{355.5}$ with a negligible memory usage.

http://www.skein-hash.info/ (the design of Threefish is based on it).
Blowfish

At this point, though, I'm amazed it's still being used. If people ask, I recommend Twofish instead.
— Bruce Schneier, Blowfish's creator, 2007

Swordfish
                         GABRIEL
              Here's the deal. I need a worm,
              Stanley. A hydra, actually. A
              multi-headed worm to break an
              encryption and then sniff out
              latent digital footprints
              throughout an encrypted network.

                            STANLEY
              What kind of cypher?

                            GABRIEL
              Vernam encryption.

                            STANLEY
              A Vernam's impossible. Its key
              code is destroyed upon
              implementation. Not to mention
              being a true 128 bit encryption.

                            GABRIEL
              Actually, we're talking 512 bit.

source


One-time pad using RSA and Diffie-Hellman functions Suppose that Alice and Bob use an encryption algorithm based on a one-way function $F$ (Eve knows it), and $r$, a secret key shared between Alice and Bob (Eve doesn't know it).
Key is computed as: $K = F(r)||F(2r)||F(3r)||...$, and the ciphertext is computed as $C = M \oplus K$, and all the blocks of $F(r)$ are $1024$-bit long.

If $F(x) = x^e \mod n$, and $(n, e)$ pair is public, will the first $1024$ bits of both plaintext and ciphertext be enough for Eve to read the entire message?

Same for $F(x) = g^x \mod p$, and public $(g, p)$ pair.

Also, are the cases described above good examples of public-key cryptography? But Eve can't encrypt only having public keys, as she doesn't have $r$. So interception of $1024$-bit long plain/cipher pair is the only way for her to obtain some information from the system.

This feels like homework, and so I won't give you the answer; I'll give you hints:

  If F(x) = x^e mod n, and (n, e) pair is public, will the first 1024 bits of both plaintext and ciphertext be enough for Eve to read the entire message?

If Eve knows the first plaintext $M_0$, and the ciphertext $M_0 \oplus (r^e \bmod n)$, how can Eve recover $r^e \bmod n = F(r)$?  Given that, how can she reconstruct $F(kr) = (rk)^e \bmod n = r^e \cdot k^e \bmod n$?

  Same for F(x) = g^x mod p, and public (g, p) pair.

Again, given $F(r) = g^r \bmod p$, how can Eve recover $F(kr) = g^{kr} \bmod p = (g^r)^k \bmod p$?

  Are the cases described above good examples of public-key cryptography?

Nope; they're not examples of public-key cryptography as all.  We know this based on your description:

  Suppose that Alice and Bob use an encryption algorithm based on ... r, a secret key shared between Alice and Bob

Public key cryptography doesn't use a secret key shared between the two parties.

Also, please don't describe these algorithms as 'one-time-pad'.  That has a very specific meaning (where the pad is generated in a truly random fashion, and not algorithmicly); this is not that.


is there cryptography algorithm space /input invariant? I'm searching for a cryptographic algorithm that produces the same result for the same input, and if in the input, at position k, there is XXXXXX, then in the output at position k there is always the field YYYYYY.

This isn't the most direct answer to your question, but you could segment your input into blocks, and just encrypt the blocks. However, performing this could possibly introduce vulnerabilities caused by being able to exploit how you're segmenting the data (if that method can't be stored in your brain).

Part of how a lot of encryption methods work is they can take a variable length input and create an output that varies size. The only encryption method I can think of that is input invariant the way you describe is a Caesar cipher.


homomorphic encryption special case of multi party computation? I read that Fully Homomorphic Encryption schemes are special case of  Secure MPC in page no 3. Especially , generalization of two party computation problems stated by Yao

But is there any additional literature showing the connections of the same ?

You've got the relationship a bit muddled.  A scheme for fully homomorphic encryption can be used to perform secure multi-party computation (MPC).  However, it's not a special case of MPC.

The connection is a standard elementary result, which I will summarize here.  If you want to do secure multi-party computation, you can express the computation as a boolean circuit $C$, and you can easily transform any circuit so that it uses only AND gates and NOT gates.  Then, it turns out that you can compute $C$ on encrypted data, if the data was encrypted using a fully homomorphic encryption scheme, using the following relationship: when working with $\{0,1\}$, AND can be done by multiplication ($x$ AND $y$ $ = xy$), and NOT can be done with addition (NOT($x$) $ = 1-x$).  Since the fully homomorphic encryption lets you do addition, subtraction, and multiplication on encrypted values, it also lets you do NOT and AND on encrypted values, which is all you need to do secure multi-party computation.


Constructing RSA private key, given public key As part of a puzzle I was given an RSA 256-bit public key and an encrypted message.

The key itself is very weak, having exponent e = 65537 and modulus N = 00:c0:fb:55:b3:ed:f5:19:bf:8d:3a:2a:60:e8:bc:6e:1c:94:f0:5c:17:19:f8:38:ff:45:0b:01:0f:47:96:27:fb

I can determine p and q by using an arbitrary precision library and iterating through until I find something that satisfies N mod p = 0, and then get q = N/p

From there it's straightforward to get phi = (p-1)(q-1) and to calculate d = e^-1 mod phi

My question is this:  Given d and N, how do I actually construct the private key as binary data suitable for use with e.g. openSSL?

OpenSSL private key format, for RSA, follows the ASN.1 syntax given at the end of PKCS#1 (the structure is then encoded with DER, then Base64, and PEM header and footer lines are added). This is easy if you know these formats, but, in practice, you will be happier if using a library which does the encoding for you. For instance, OpenSSL (the library) lets you create a private key as a bunch of big integers (because that's what a RSA private key is -- again, read PKCS#1).

That being said:

  I can determine p and q by using an arbitrary precision library and iterating through until I find something that satisfies N mod p = 0

I hope you are patient !

(Hint: read this. Factoring a 256-bit integer is feasible, but not immediate. You'll need a bit of computing with a smart algorithm like quadratic sieve.)


What are KDF parameters in OpenSSL command-line utility for `enc`? I refer to https://www.openssl.org/docs/manmaster/apps/enc.html and see that the only parameter for key derivation which I can set explicitly (not considering the obvious -S for setting salt) is -md which is MD to be used for key derivation algorithm.

Now the question is: what are other implicit parameters for KDF when using OpenSSL in cmd mode? In particular, does it use PBKDF2? And if so - the most important question: what is the default value for number of KDF iterations? I can't find those values.

I am using OpenSSL cmd utility to encrypt plaintexts. The result is decrypted using another crypto library. I need to test password-based encryption in particular.

To make it more clear: I want to save generated salts and passwords, then decrypt ciphertexts with another crypto library which does use PBKDF2 with HMAC_SHAxxx algorithms and gives the opportunity to set number of KDF rounds as well. So I want to have a possibility to derive exactly same keys from passwords and salts as OpenSSL cmd utility does.

Finally, maybe the idea to rely on cmd utility is somewhat bad considering my task. If so, I want to hear your opinion on this, too.

I've got OpenSSL 0.9.8zh 14 Jan 2016 (OS X).

OpenSSL uses EVP_BytesToKey, an algorithm proprietary to OpenSSL, with a salt and an iteration count set to 1. The algorithm is secure; the iteration count of 1 of course is not secure (for passwords with an average strength). Implementations for other languages/runtimes can be found by searching for it by name.

This page (on nabble.com) explains a bit about accessing PBKDF2 from the command line. It also shows that OpenSSL CLI isn't always taken that seriously; OpenSSL is mainly a cryptographic library that can also be used from the command line.

It is possible to find code to include the iteration count in the CLI in the answers to this question on the security site (not reviewed by me). That code is however specific to private keys encrypted using the PKCS#8 standard.

It could well be that PGP is more suited for end-to-end password encryption (I haven't reviewed it for a while). It was certainly more specifically created for it.


A hash-based pseudorandom function Let $H()$ be a cryptographic hash function.

Question: Can we consider $c= H(r||i)$ as a pseudorandom value, where $i$ is a public value, $1\leq i\leq n$, and $r$ is a large uniformly random value/key?

Edit (added after 1st comment was provided): $i$ values are just integers, $r\xleftarrow{R}\mathbb{F}_p$, where $p$ is a sufficiently large prime number. Note that we want to use the above function for multiple $i$'s where $r$ is used for all but kept secret.

Yes, only if $H(-)$ is either a $\texttt{HMAC}(-, k)$ function or an hash algorithm resistant to Length-Extension attacks1, for example, the Blake2 hash algorithm2. I'm assuming too the collision/preimage resistance, so it would be unlikely to 2 different pairs $r \ne r'$ and $i \ne i'$ collide on $H(r || i)$ = $H(r' || i')$. In this case, the $i$ index would be the key $k$ for either $\texttt{HMAC}$ or keyed-mode of the length-extension resistant hash. In fact, it is mostly how the Bitcoin HD wallets3 work to generate one-time addresses.

Due the deterministic nature of hashes, you must never reuse the same $(r, i)$ pair to generate pseudo-random values. But due this deterministic nature too, this kind of PRF is used to generate entropy where public randomness is needed, e.g, on Blockchains. On the literature, they are called Provably Fair Algorithms4,5. In such contexts, the verifiable/reproducible nature is really important to protect against cheating, the $r$ entropy would be sealed under a commitment to be revealed later for verification.


True/False if a user is a customer without revealing the actual customer I have a user A and a third party company B. I want to check if A is a customer of B.

B cannot reveal any information about their customer list to me.
If A is a customer of B, I do not want B to know which customer they are. They should only know True/False answer to wether they are a customer.

What sort of problem is this? I thought this might be a private set intersection problem but the definition seems to violate my second condition. Is this instead a Zero Knowledge Proof problem?

"Private set intersection (PSI) allows two parties to compute the intersection of their sets without revealing any information about items that are not in the intersection."

A 1-out-of-n Oblivious Transfer protocol would fit as a solution to your problem.

Oblivious Transfer can be viewed as an improved Private information retrieval protocol, because it allows that only exactly 1 item is retrieved from the database, without sharing any additional info about the database. In addition the "sharer" of the database ($B$) doesn't learn about which item ($A$) was retrieved.

If $A$ is not a customer of $B$ then $B$ should only return information in a way to make it clear to you that $A$ indeed is not a customer and not any information  more should be disclosed by $B$.

Tung Chou and Claudio Orlandi have designed a relatively easy to understand 1-out-of-n OT-protocol, appropriately named The Simplest Protocol for Oblivious Transfer. The math used for this protocol is almost the same that is also used for Diffie-Hellman key exchange.

If you really want a computationally efficient protocol, then the OT-protocol designed by
Moni Naor and Benny Pinkas (Computationally Secure Oblivious Transfer) is more appropriate.


Who assigns algorithm OIDs for cryptographic algorithms? I am aware that this is at the border to security but I guess that I will rather find an answer here. The question is which institution generally assigns object identifiers for cryptographic algorithms so that they can be used in higher level protocols (with corresponding adoption of standards). I am aware that theoretically everyone can become an OID registry but I guess there is one that takes care of cryptographic algorithms.

No, there isn't a single one that takes care of the algorithms. Many algorithms do not have an OID, and many proprietary ones have OID's that aren't known.

The OID's are strictly hierarchical. The first digit is either 0, 1 or 2 indicating ITU-T, ISO or both. ITU-T and ISO are both international standards organizations that are then responsible for the next digits. This may include internal associations, but they may also be other organizations. Those organizations are then responsible for their part of the tree.

Of course, if anything is standardized by e.g. ISO then it will probably get an identifier somewhere in the tree of ISO. It could however be that the algorithm is already registered somewhere else, and in that case it may not get a new one. Or it could and you would have two ones identifying the same thing. It is up to the protocols to choose which ones you should use.

As there isn't one global registration authority for the insurmountable amount of algorithms, there isn't a single location in the tree either. And there doesn't need to be: an ID doesn't need to be ordered.

Commercial entities

It is perfectly possible for a commercial organization to get their own space in the OID tree:

{iso(1) member-body(2) nl(528) nederlandse-organisatie(1) enschede-sdu(1006)}

This space seems empty but the organization no doubt build their own tree internally. In this case I have very little doubt, in fact.

Examples

{joint-iso-itu-t(2) country(16) us(840) organization(1) gov(101) csor(3) nistAlgorithm(4) aes(1) aes128-CBC(2)}

So here the joint ISO / ITU-T has created a space for countries, and those countries can decide how to create their trees. Here CSOR is part of NIST, which has created a subspace for AES and then CBC mode.

 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1) rsassa-pss(10)}

Here ISO identified the US, who has identified the RSA digital signature algorithm, PKCS#1 / PSS version.

{iso(1) member-body(2) us(840) ansi-x962(10045) signatures(4) ecdsa-with-SHA2(3) ecdsa-with-SHA384(3)}

Same thing, but now a national standardization institute: ANSI has created a standard with associated OID's.

Configuration

Important note: there are generally two ways of handling algorithms and OID's in data structures such as ASN.1, shown in the following X.509 (certificate) specification:

 AlgorithmIdentifier  ::=  SEQUENCE  {
      algorithm               OBJECT IDENTIFIER,
      parameters              ANY DEFINED BY algorithm OPTIONAL  }

every algorithm is fully identified, including any configuration option and the parameters are not present or NUL
the algorithm is specified, but it requires additional parameters to be specified.

You can see this in the above examples where the ECDSA algorithm is defined with the hash, while RSA PSS requires additional configuration parameters.

Structure?

For some fun, please see the following quote in the OID database here:

  To the question "Are the OIW OIDs still in common use?", Peter Gutmann replied on June 23, 2004: "Some of the crypto ones still in use, this would include the DES-modes OIDs and some of the weird (obsolete) Secure Hash Algorithm (SHA) and Digital Signature Algorithm (DSA) ones that were (incorrectly) copied into Java Cryptography Extension (JCE) implementations. Examples of obsolete OIDs: {iso(1) identified-organization(3) oiw(14) secsig(3) algorithms(2) sha-1WithRSAEncryption(29)}; an obsolete DSA one that ended up in Common Data Security Architecture (CDSA) (so presumably "OS X crypto" will use it) and the German Public Key Infrastructure (PKI) work; and a variety of other odd bits and pieces. In general you need a many-to-one mapping where on write you emit the most appropriate OID and on read you allow any one of a number of OIDs, including incorrect ones (the Java Development Kit (JDK) one is actually dsaWithSHA0, but it's used as if it was dsaWithSHA1)."

Please do not expect all that much structure in the OID tree.


Standard format to store text in LSB steganography? I am trying to understand how text is stored in images in LSB.

If we consider a 24 bit image, we have 3 values per pixel (RGB). So we can store 3 bits in a pixel. So how do we store 'A' or any other character in this situation? Do we store 6 bits in 2 consecutive pixels and then last 2 bits in RG of next pixel and then start storing the first bit of next character from B of the same pixel?

Also, is there a standard for this? E.g. should we start from the first pixel always? If not, is there a way to guess by looking at the pixel values from where the data is stored?

There is no standard. But since the goal of steganography is undetectability, it is not usual to hide data into consecutive pixels. Steganography hiding data into all the pixels is broken.

Some algorithms use a function that detects areas of the image where the insertion produces less distortion along with a PRNG.

See, for example:
https://hal.archives-ouvertes.fr/hal-00541353/document


What operations are used in symmetric cryptography and why? In continuation to Why are bitwise rotations used in cryptography?: what other operations are commonly used in symmetric cryptography? Are there particular operations on numbers that are good for building ciphers? Do common ciphers tend to use the same basic building blocks?

Some similar questions:

Why Addition Mod 32?
What exactly is addition modulo $2^{32}$ in cryptography?

which else operations are used in cryptography and why?

This question is hopelessly broad, but I'll give the "which" a shot. Ignoring asymmetric constructions like RSA, cryptographic primitives typically stick with operations that are either a single instruction in common architectures or can be implemented cheaply with a combination of a few instructions. Thus, bit rotations, arithmetic addition, logical bitwise operations like AND, OR, and XOR, and so on, are all good candidates for operations. Table lookups are also quite common to speed up implementations.

It's not really the operations themselves that are so important, however. The way you combine them is (obviously) far more important, and hence unless you have a specific question about why a specific operation has so much use, it's not really all that relevant to ask "what operations are used". Instead, study things like how the Merkle–Damgård construction can be used to build a hash function, how a substitution-permutation network can be used to build a block cipher, how HMAC can transform a relatively weak hash function into a good MAC. If you would like more examples, I can provide them.

These are the important building-blocks of primitives, not necessarily the operations underlying them. The operations are obviously important, but don't miss the forest for the trees.

On the other hand, you have the mathematical schemes, for lack of a better term. These use mathematics to achieve some goal, and hence the "operations" in them are virtually limitless. RSA and Diffie-Hellman both use modular exponentation, though in different ways; Shamir's secret sharing scheme relies on the idea that a $n$-degree polynomial can be uniquely identified with $n+1$ points, and so uses polynomial evaluation in a finite field as well as Lagrangian interpolation; the Merkle-Hellman knapsack cryptosystem relies on the subset-sum problem; and it just goes on and on.

There are zero-knowledge proofs, secure multiparty computation schemes, cryptographic voting schemes, fully-homomorphic encryption schemes, functional encryption schemes, identity-based schemes, ... the bounds are limitless. Trying to exhaustively list the operations used here is futile.

My point is that cryptography is a vast field. There are operations aplenty, but far more interesting are the schemes themselves. The operations are just means to an end.

  What is the difference between addition modulo 2 (xor) and addition
  modulo 2 ^ register size (addition with overflow)?

XOR is not just "addition modulo 2"; it's bitwise addition modulo 2, and I dislike this definition. The point of bitwise exclusive-or is that the output of each bit is 1 if and only if the two input bits are different. Hence, it is an exclusive-or: exclusively, one of the bits may be turned on. If both are on, or both are off, the output is 0. This property makes XOR an involution, i.e. a function that is its own inverse. Bitwise-AND and bitwise-OR are not invertible.

Addition modulo 2^{register size} is just what it says on the tin: the addition can overflow or underflow.


Is TrueCrypt's multiple/cascading encryption safe? Is TrueCrypt use of cascading encryption safe?  Is it useful?  TrueCrypt is arguably one of the most popular and widely used encryption applications in use today, yet it seems to use a very unconventional scheme.

The software offers cascading encryption, where the user can specify either double or triple encryption using any combination of AES, Twofish, and Serpent.  Unusually, multiple-encryption is performed on each block, before moving on to the next block, as opposed to encrypting all the data and then encrypting the resulting ciphertext.

After having spent a lot of time reading through crypto.se, the consensus seems to be that multiple/cascading encryption offers little (or perhaps no) extra security, and some even argue that if may be weaker than just following a standard protocol (although the latter rarely seems to be substantiated by any reasoning).  However, in Bruce Schneier's Applied Cryptography (considered by many to be a quintessential text on cryptography), he advocates the use of multiple encryption (albeit cautiously, and with some caveats).  See sections: 15.7 Cascading Multiple Block Algorithms, 15.8 Combining Multiple Block Algorithms, and 17.11 Cascading Multiple Stream Ciphers.

Another example of going against this consensus would be the Tahoe-Lafs 100 Year Cryptography Project, which has been recommended on crypto.se. Their protocol involves encrypting with AES in CTR mode and then encrypting the output with XSalsa20.

So my question is, is TrueCrypt's use of multiple/cascading cryptography reasonable, and why?

Cascading cipher gives a sense of security; and one that is technically justified with respect to the possibility that a weakness in one of the cipher would allow recovering the encrypted data. That's Bruce Schneier's argument, and it made sense in an era where DES, the then leading cipher, was a closed design, clearly deliberately weakened by a small key, giving rise to the fear that is was also deliberately weakened otherwise (which turned out not to be the case).

On the other hand, the more serious threats facing systems like TrueCrypt are not a weakness of the cipher; they include compromise of the software, compromise of the hardware running the software, compromise of the key (by eavesdropping, guess of the passphrase, rubber hose cryptanalysis, recovery from hibernation file or RAM memory..), analysis of changed sectors.. These risks are hard to mitigate, and in the opinion of many (including me), much more likely to materialize than cryptanalysis of AES, for at least decades even if we consider AES-128. And further, technological progress likely will enable a guess of the passphrase by brute force sooner than a cryptanalysis of AES.

Cascading ciphers has at least one obvious drawback: performance is lowered. Often it matters, sometime it does not, e.g. when enciphering a key. In my opinion, compared to AES, cascading might only improve practical security by a side effect: making it harder to verify a guess of the passphrase (that would be the case in a system where the only way to check such guess is to turn the passphrase into keys, decipher something using the cascade of ciphers, and check that it makes sense).

So all in all, I would think of cascading a cipher in addition to AES only as a way to damp paranoia or indicate an extra level of care, like telling to someone knowing little about cryptography: for the cold storage of your all-important master keys, you could use a Truecrypt volume on a USB stick, perhaps even with cascaded ciphers; and most importantly, strive for the integrity of all the hardware and software used!

Addition following comment asking how to do cascading (of block ciphers) properly. My answer to that would be that if one uses cascading:

That might be considered in the key-stretching phase (turning the user's passphrase into the key of the bulk cipher), where cascading is useful, because it makes construction of a device that successfully brute-force passphrases significantly harder/more expensive/less likely. Cascading is useful in key stretching because when a cascade of encryptions is iterated, a fast implementation must be fast on each of the cascaded ciphers, which is a very serious problem in a password cracker using ASIC or FPGA; search FPGA password for some interesting links. Beware however that speed optimization of the legitimate implementation for each of the cascaded cipher iterated in the key-streching phase is important for security (because we need to push the number of iterations as high as feasible), when it is immaterial to security in the bulk-encryption phase.
At least the first cipher in the cascade (the one in contact with the plaintext during bulk encryption, or to a lesser degree the one in contact with the passphrase during key stretching) should be implemented in a manner protecting from any likely side-channel attacks, including timing and unwanted emissions (for an illustration of that later danger in a slightly different context, see this).
When the key must be secret (in particular the key used for bulk encryption), the cascaded ciphers positively must use different keys (e.g. extracted from a wide derived key); otherwise using a cascade could well turn out to enable an attack if any of the ciphers turns out to leak its key through a side channel.

Truecrypt's use of cascaded ciphers definitely follows 3; I can't tell for 2, and the most important 1.


How to build an electro-mechanical public key cipher machine? It is generally assumed that asymmetric encryption schemes were invented in 1973 at GCHQ in Britain and, independently, in 1976 at the MIT.

Imagine, if the abstract idea of having a public key and a private key that can only decrypt what has been encrypted with the other, respectively, had been around forty years earlier. Would it have been possible to build a working (rotor) cipher machine using this principle with WWII technology (think public key enigma)?

Are there any public key encryption  schemas that have sound mathematical basis and can also be implemented using electro-mechanical machines without transistors?

Since this is an historical question, I am going to digress and make some historical corrections. In science, we give credit for important inventions to the people who published. If it turns out that someone else invented it earlier and didn't publish, they don't get credit. Obviously, they should be mentioned in passing or a footnote in the interests of complete information, but credit for inventing something goes not to the person who keep it secret, but to the people who publish.

Thus, I must take issue your saying that GCHQ invented it. As smart and forward-thinking Ellis, Cocks, and Williamson were, they didn't publish, so they don't get credit for inventing it. (Also, they were at CESG, not GCHQ. Some may find this a difference without distinction, but Ellis himself makes that point in his notes on their work.

Secondarily, public key encryption is generally credited to some combination of Merkle, Hellman, and Diffie, who were at some combination of Stanford (where it was understood) and Berkeley (where it was misunderstood). Diffie's article, "The First Ten Years of Public-Key Cryptography" is a great account of this. You can also find Merkle's rejected 1974 Berkeley project for what was an early form of public-key cryptography on his Computer History Museum bio.

Thank you for your forbearance on the above. Now let me answer your question.

The basic idea in public-key cryptography is that there are problems that are easy to do in one direction and hard to do in another. At it's easiest, this is intuitive. Anyone who has struggled through learning long division knows that there's a very real sense in which dividing is harder than multiplying. But more more importantly, the structure of public-key (or non-secret) encryption is that there's one key to encrypt and one key to decrypt and you can't derive the decrypt-key from the encrypt-key. That's why the encrypt-key is either public or non-secret.

In construction, the Merkle-Hellman-Diffie ideas played around with "trapdoor" functions that had a secret that made the problem very easy to solve. The basis for discrete-log public key cryptography is that exponentiion -- $g^x$ in a finite field with a public $g$ and a secret $x$ is easy to solve for the person who knows $x$, but hard without knowing the trap door of $x$.

Similarly, RSA is built on the difficulty of factoring, and the trap door is that if you know the two primes you've multiplied together, it's easy to undo an RSA calculation. Rabin is based on the hardness of square roots (think of it being a special case of RSA where the public exponent $e=2$), and so on. Just as it's easy to intuit that division is harder than multiplication, taking a logarithm or a square root or factoring is intuitively a lot harder.

So how does this apply to electro-mechanical systems? Well, you could probably construct an electromechanical machine that did Diffie-Hellman. Konrad Zuse's Z3 computer was Turing-complete and program-controlled. It's entirely possible you could do it there. I have a mild raised eyebrow as the Z3 didn't have conditionals, but if you knew about Diffie-Hellman or RSA, I'm sure you could build a machine to do it. Of course, you'd have very short keys, but who cares, as everyone else only has electro-mechanical machines, too.

Could you do it with rotor machines? I don't know. My intuition is to say no. Remember that what we want to have with public key machines is a separate encrypt and decrypt key, and fast decryption aided by some trap door. Enigma was in many ways a mechanical puzzle in which electricity was bounced around, whereas the Lorenz machine is pretty recognizable as a modern stream cipher. I don't see a good way to turn those into public key systems.

For quite some time, we cryptographers have considered the possibility of symmetric ciphers that had some sort of back door in them. Some number of years ago, someone proved that if you have a symmetric cipher with a back door, then that is a trap-door function that can be used make an effective public key cryptosystem where the backdoor and its parameters are the secret key. (I'm sorry that I don't remember whose theorem that is.) Interestingly, this would be a public-key system that runs at the speeds of a symmetric cipher and very likely with a key that is small (compared to other public-key systems).

All our usable public-key cryptosystems are much, much slower than symmetric systems. They're often four or five orders of magnitude (or more) slower than symmetric systems of comparable strengths. So if you managed to find one of these, why would you waste it by releasing it as a symmetric cipher with a back door?

If you're an academic, you've invented something of mindblowing newness. It's an invention at least as powerful as the existing public key systems, and really much, much more interesting because it runs at symmetric speeds.

If you're in an intelligence service (like the CESG guys), you still have something amazingly powerful. Would you waste it? I say waste, because if you release this new cipher as a symmetric cipher, someone's going to figure out the back door eventually, even if that happens by a leak. Someone else will figure out that it's actually a usable public key cryptosystem and they will get the credit for it, not you. If and when it comes out that you knew it all along, then the way history will remember you is for this, and history is unlikely to be kind.

Moreover, this suggests that at the very least, making either a fast public key system or cipher with a backdoor is very hard. We've been trying for ages to get effective, new, usable public key cryptosystems and they're hard to do.

This means that if there is a way to make a rotor or electromechanical system that has a new public-key cryptosystem (one that isn't simply one of the ones we know now), we very likely don't know it. That suggests that they really couldn't have done it then. It's more likely tha they'd have done something like invent Diffie-Hellman or one of Merkle's puzzles or knapsacks and then implement that on electro-mechanical hardware.

So I would say that no, probably not. People in WWII probably could not have come up with something cool that isn't one of the systems we know about now.

Jon


Using SHA1 to obfuscate published resource IDs First off, yes I do know that SHA1 is cryptographically insecure (and has been for a long time). So this question is more academic than anything. It's also very contrived, but bear with me.
I want to publish a table of string IDs with timestamps, but at the same time I don't want somebody to be able to look at the table and use it to enumerate all the resources available.
TmQ5YqqOOPPiEewdntZx  2021-05-05 13:26:38
SVQBu941OWIyDXzSgo2F  2021-05-05 13:26:44
gkxMiz6hEPqV36TidyeG  2021-05-07 09:56:43
vU2OxFFQ4I0gXHGofL8A  2021-05-07 09:56:43

So I can hash the IDs in the table (HMAC is pointless, as the client would need to be aware of the secret used by the table generator):
d3399d662fc58daf44647f188cb6ef30bf76938c    2021-05-05 13:26:38
fc95d2f3af27034ff5a991d5b9a0080cbf45d007    2021-05-05 13:26:44
cd982afcff4ae5e907960f51ae1504a38f4665d1    2021-05-05 13:53:42
e0f31185494f54a3a16ac3483572989f98850c36    2021-05-07 09:56:43

A client, who already knows an ID can hash it, look it up in the public table and check the timestamp. The table should be useless for anyone who doesn't already know an ID.
My thoughts are:

Even though SHA1 is cryptographically insecure, I'm not using it for verifying the ID, but using it for obfuscation
Even if somebody can generate a collision, it doesn't give them the ID needed to request the resource
I don't want to use SHA2 as the shortest hash I can generate is 256 bits, which consumes 60% more storage (imagine I have a lot of them, and I'm very cheap!).

Obvious response will be:

Just use SHA2, and it's a valid response. I could just truncate the hash if I'm that concerned about storage space and transfer costs. 160-bits is still a larger address space than 62^20, so collisions are unlikely
Just SHA2, it's faster than SHA1. Yes it is, and actually SHA512 is faster than SHA256 (in .Net anyway)
Use something else.

If #3, please let me know.
Obviously, I'm going to use SHA2, but is there a cryptographic reason for not using SHA1 (or even MD5 if I was feeling really retro) in this instance. Like I said, the question is mainly academic.

(should I) use something else (than SHA-1)?

Yes. That seems to be a good application of purposely slow hashes intended for password hashing, like Argon2id, or it's ancestor scrypt, or (if all else are unobtainium in the context) SHA-2 followed by bcrypt (don't even google PBKDF2-HMAC-SHA-1, which is obsolete).
These are like SHA-1, less cryptographic break of it's resistance to collision, plus an output size parameter, a plethora of extra inputs for key as HMAC or/and other salt/associated data should that be needed. And most importantly parameters to tune the execution speed; with the whole thing crafted in a way such that adversaries using GPUs or ASICs for brute force search of valid string won't gain so much advantage over using a CPU, as legitimate users do.
This will let you increase security significantly at equal size and number of IDs, or/and safely reduce size of IDs. Just tune the parallelism parameter to the minimum number of physical threads on all platforms using the system (perhaps less 1 or 2 to keep the thing user-responsive, but with a minimum of 1; use 1 if in doubt); memorySizeKB to the lowest free RAM available on all platforms (for all threads, less a fair safety cushion, including for launching the stated number of threads/processes); then up iterations to what's tolerable on all platforms.


Is there a relationship between the secp256k1 public key of the sum of two private keys, and the public keys of those original two private keys? If I have two secp256k1 private keys and add them together, can I derive the public key for the sum, if I only know the public keys for the two original private keys?
(I think this may be the core of understanding bip32.)

If I have two secp256k1 private keys and add them together, can I derive the public key for the sum, if I only know the public keys for the two original private keys?

Yes.
While the idea of 'public keys' and 'private keys' depends on the cryptosystem (and not the elliptic curve it uses), most ECC-based cryptosystems (including the one used in bitcoin) have a private key that is a secret integer $a$, and a public key that is the elliptic curve point $[a]G$, where $G$ is a publicly known elliptic curve point (which is part of the definition of the curve), and $[a]G$ is computed using 'point multiplication'.
So, your question boils down to "if we know two public keys $[a]G$ and $[b]G$ (with private keys $a$ and $b$), can I derive the public key $[a+b]G$, which is the public key for the sum of the private keys?"
The answer is, yes, because this identity always holds:
$$[a+b]G = [a]G + [b]G$$
where the addition on the left side is integer addition, and the addition on the right side is point addition.  The right side is easy to compute, when we can get the public key for the sum of the private keys.


How to learn the first bit of m in padded RSA Consider the following version of padded RSA encryption, where encryption of $m$ is done by setting $m′ = (0^k~||~r~||~00000000~||~m)$ for a random $r$ (of length 8 btyes = 64 bits) and then computing the ciphertext $c = (m′)^e$ (mod $N$). For concreteness, further assume that $N$ is a 1024-bit RSA modulus, and that the scheme only handles 512-bit messages.
For the rest of the problem, assume you are given some ciphertext $c$ that is the encryption of some 512-bit message.
Suppose you learn that $(2^e)c$ (mod $N$) is a valid ciphertext. What does this tell you about the first bit of $m$?

I assume that this is a homework problem, and so I won't give you the answer.  However, here are a few hints:

What does 'it is a valid ciphertext' mean?
If $c$ decrypts to the value $m'$ (not counting the depad operation; that is, if $m' = c^{1/e} \bmod N\ $), what does $2^ec \bmod N\ $ decrypt to?  What is the relationship to those two values?


Implementing AES in C++: 4x4 Array of unint8_t, or 4x1 array of uint32_t? I'm implementing AES in C++, and, inspired by the way words are handled in SHA, I decided this time to handle the state as a one dimensional array of 4byte unsigned integers as opposed to a two dimensional array of bytes. To get the bytes out of each of word, I use shifts and mod. E.g. to get the first byte in state[0], I would retrieve byteA = (state[0] >> 24); and to get the second, byteB = (state[0] >> 16) % 256;

In the mix columns and substitution steps, I have to extract and replace bytes from the word, but in the shift rows and add key steps, I can operate on an entire row at once, eliminating the need for 4 extra iterations per row.

Unless this would be very specific to my implementation, I'd appreciate some input on which might be faster.

One way to see it is the following: RAM is slow. Modern processors can do several operations in a single clock cycles. However, a RAM access, such as retrieving data from an array based on a computed index, has inherent latencies and concurrencies issues; in the best of cases, you can do one memory access per cycle, and the result is not available for computations until at least one or two cycles later (even if all the data is in L1 cache).

Therefore, generically, it is best to do as little array accesses as possible. Which means grabbing from each array access as much data as possible, such as a full 32-bit word instead of just one byte.

The trouble with generic comments like the one above is that they are, well, generic. Performance issues depend a lot on the involved architectures, the operational constraints, and what you want to achieve; there are several metrics of performance, such as bandwidth, latency, code size, energy consumption... So, really, you have to try. However, most people (including myself) who have tried to implement AES on 32-bit processors (like a PC or an ARM CPU) with at least a few kilobytes of L1 cache, and no hard limit on code size, have found the "32-bit word" structure to be the best -- unless you aim for an implementation which resists to cache timing attacks, in which case you have to do things quite differently, without any array at all.

To investigate the ins and outs of AES software implementation, you could do worse than perusing Brian Gladman's site which is kind of a reference on the subject.


How to disguise ciphertext If I want to have a secret conversation, then I can encrypt it (with OTR etc). However, since big brother watches all communication, sending encrypted data will likely raise flags. Does anyone know of an algorithm to take ciphertext and convert it into harmless looking plaintext?

For example, I could take each group of three hex digits, like "3E8" and convert it to an english word, like "peanut". So "2E8A983F7E100B6CE1" gets converted to "fork would said free dish quark". But I think that would still be pretty easy for big brother to detect.

Anyone know of a good algorithm for this? Anyone seen any research on it?

EDIT: Imagine two people want to communicate securely over a channel, but the channel only allows plaintext. If the channel doesn't understand the message, it will block it. So they have to find a way send a strong encrypted message that looks like plaintext.

What you are looking for is called steganography. It is a different field from cryptography so you might want to check in some other fora also.

I don't know much about steganography but i remember this paricular algorithm. You can take you ciphertext, and an image say a greyscale bitmap. Then you can replace the least significant bits of every pixel with a bit from your ciphertext. Since ciphertext are "random" bitstrings one would no be able to recognise a ciphertext from random noise on the pixel values.

You can then reconstruct the ciphertext by reading the last bit from each pixel.


Complexity to find an preimage of a hash function Suppose a hash function based on Merkle-Damguard construction. Its compression function is given as $H_i=E_{m_i}(H_{i-1})$, where $E_{m_i}()$ denotes the encryption of an ideal block cipher with $n$-bit block size. What is the lowest complexity to find an preimage of this hash function?

Answer: By applying meet-in-the-middle attack, the complexity of finding an preimage is $2^{\frac{n}{2}}$.

The answer above is provided  by lecturer. I don't understand how to apply meet-in-the-middle attack in this question.

For an $n$-bit hash with at least $n/2$-bit block size  (which is very common and includes MD5, SHA-1, SHA-2, SHA-512), using a round function as in the question, here is how to find a 2-block message $m_0\|m_1$ hashing to given $H$ with effort $O(n/2)$.

I note the Initialization Vector $H_{-1}$ in order to match the question's recurence $H_i=E_{m_i}(H_{i-1})$. Hashing $m_0\|m_1$ requires 3 rounds, with the third processing the padding block $m_2$, which is known, and the result $H_2=H$.

We compute $H_1=E^{-1}_{m_2}(H)$. This is possible since $E$ is a block cipher and allow decryption. Notice that would not be possible with $H_i=E_{m_i}(H_{i-1})\oplus H_{i-1}$ as in the Davies-Meyer construction (used in SHA-1 and SHA-2 with a small modification).

For $2^{n/2}$ incremental values of $m_1$, we computes and make a list of $E^{-1}_{m_1}(H_1)$. It is possible that we get some collision(s) there (probability about 39% that we get at least one), but unlikely that we get more than a few, thus we likely have just shy of $2^{n/2}$ distinct values in the list.

For $2^{n/2}$ incremental values of $m_0$, we computes and search in the above list $E_{m_0}(H_{-1})$. There is good probability (>63%) that at least a match is found.

A corresponding $m_0\|m_1$ (if any) is our message hashing to $H$.

Note: we can reduce the message size to one block and about $n/2$ bits.

As is, the attack uses $O(2^{n/2})$ memory. However, that can be reduced to practical using Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website).


Function to polynomial equation in GF(2) Let F(a,b,c,d,e) be a function that returns the ith bit of 0x3A5C742E, where i=a*2^4+b*2^3+c*2^2+d*2+e and i is the offset from the least significant bit.
The author Page 33/200, chapter 2.3.4 states that in order to find the polynomial for the equivalent output you can use k-maps.
Later he states that the equation after the calculations is:

NLF(a,b,c,d,e) = d+e+ac+ae+bc+be+cd+de+ade+ace+abd+abc

Here is my k-map calculation:

     00   01   11   10
000   0    1    1    1
001   0    1    0    0
011   1    1    0    1
010   0    0    0    1
110   0    1    1    0
111   1    1    0    0
101   1    0    0    1
100   0    0    1    1

Where rows are abc, and columns are de

Now from this figure I cannot see how it is possible to generate the given equation. There are elimination of only 1 variable. So all the generated equations should have been at least of 4 degree.

So the question is, how is his equation generated?

The formula
$$ d+e+ac+ae+bc+be+cd+de+ade+ace+abd+abc $$
is in algebraic normal form (ANF).
That is the unique representation of our boolean function with respect to the $\mathbb F_2$-basis $\{a^ib^jc^kd^le^m\mid i,j,k,l,m\in\{0,1\}\}$ of the space of boolean functions $\mathbb F_2^5\to\mathbb F_2$.
In particular, note "$+$" is exclusive or.

I do not think the Karnaugh map is very helpful in that case, since grouping the $1$ entries in the table becomes a bit tricky, and since you have to avoid negations. In the end, it works, but it's more involved than just drawing a few rectangles and reading off the right terms.

Instead, the algebraic description above provides an easy iterative method to compute the ANF. (See also this Math.SE post.)
Basically, the ANF for our function $f$ will look like this:
$$
f(a,b,c,d,e) =
x_0+
x_aa+x_bb+x_cc+x_dd+x_ee+
x_{ab}ab+x_{ac}ac+x_{ad}ad+x_{ae}ae+x_{bc}bc+x_{bd}bd+x_{be}be+x_{cd}cd+x_{ce}ce+x_{de}de+
x_{abc}abc+x_{abd}abd+x_{abe}abe+x_{acd}acd+x_{ace}ace+x_{ade}ade+x_{bcd}bcd+x_{bce}bce+x_{bde}bde+x_{cde}cde+
x_{abcd}abcd+x_{abce}abce+x_{abde}abde+x_{acde}acde+x_{bcde}bcde+
x_{abcde}abcde
\text,
$$
and we are interested in computing the unique coefficients $x_\ast\in\{0,1\}$.
To do so, we restrict the target function $f$: Setting enough variables to zero will simplify the above formula sufficiently to fully determine another coefficient.

To start with, we consider the "restriction" $f(0,0,0,0,0)$. By the above formula, this is just $x_0$.
Next, we consider $f(a,0,0,0,0)=x_0+x_aa$: Since $x_0$ is already known, $x_a$ may be recovered as $f(1,0,0,0,0)+x_0$ (modulo $2$ of course). The coefficients $x_b$ through $x_e$ are computed analogously.
For $x_{ab}$, consider $f(a,b,0,0,0)=x_0+x_aa+x_bb+x_{ab}ab$: The coefficients $x_0$, $x_a$ and $x_b$ are already known, so we can compute $x_{ab}=f(1,1,0,0,0)+x_0+x_a+x_b$. Again, $x_{ac}$ through $x_{de}$ work exactly the same.
Repeating this procedure will eventually yield all the coefficients.

In case you just want the result without going through the process manually, note that sage provides the relevant functionality.