Can it be done? Securing physical badges with cryptography

This is actually a fairly standard cryptographical problem, with standard solutions.

The easiest solution would be to use a Message Authentication Code; this is a function that takes a key and a message (in your case, the text on the badge), and produces a random-looking code.  What you would do is initially pick a random key, and give that key to both the guy producing the badges, and also install it into the scanner.  When you create the badge, you take the text and the key, send it through the MAC, and generate a value, which you also put on the badge.  When the scanner reads the badge, it takes the text it reads (excelt for the MAC value), and the key, send that through the MAC, and generate the value, and see if that's the value on the badge.

Obviously, this very straight-forward, and we have MACs for which the best known way to generate a forgery is to select a random value, and hope that value happens to be the correct one (which can't be verified until you actually scan the badge); if you have a 10-15 digit value, this would almost certainly be detected.

This meets all your requirements, and just has one problem; the MAC key needs to be installed in the scanner.  If it's possible that someone can steal a scanner, open it up, and recover the MAC key, this breaks the entire system.

If this is a viable attack, then the next step is to use a signature operation (such as ECDSA as mentioned in the comments); this works similarly to the MAC, except you generate two keys, a private one (which you use to create the badges), and a public one (which you use to verify the badges).  The public key can verify a badge, but (here's the cryptographical magic) it can't be used to create new ones.  The problem is the signature size; public key signatures are always rather larger then the corresponding MACs.  The comment says that an ECDSA signature could fit into about 32 bytes; this assumes an EC curve that could be broken by a large institution (circa $O(2^{64})$ effort), and so might not serve your purpose.  A 64 byte ECDSA signature, on the other hand, should be good against any adversaty; if you can fit 64 bytes into a QR code, that might be a viable alternative.


Is OpenSSL HMAC vulnerable to length extesion attacks when using MD5 as hash algorithm?

HMAC-MD5 is not vulnerable to length-extension attacks, period.

If that's what your code computes, then your code is not vulnerable to length-extension attacks.  That said:

Length-extension attacks are a part of the protocol, not an implementation of the protocol.  It doesn't matter whether you use OpenSSL or something else to implement the same protocol.

You should have a concise description of your protocol and generate test vectors, e.g. with Python or Go, to confirm that your C code is computing the cryptography you intend in the protocol.  You should also have a clear statement in a design document of what your protocol accomplishes, without reference to the cryptography it uses; and a clear statement in a separate section of the design document of what security goals your protocol aims for.
Your code has another problem: it has a side channel leak that could be exploited to forge messages, because you're comparing secrets with memcmp.  In OpenSSL, you should use CRYPTO_memcmp instead.


Looking for a specific cryptosystem (encryption two times with two different keys and then decryption with another different key )

The standard answer to this is the Pollig-Hellman cipher.

Here's how it works; you have a large public prime $p$, and each key $k$ is a value relatively prime to $p-1$.  Then, we have:

$$E_k(M) = M^k \bmod p$$

$$D_k(M) = M^{k^{-1} \bmod p-1} \bmod p$$

What this means is that we have:

$$E_{k_2}(E_{k_1}(M)) = E_{k_1 \cdot k_2 \bmod p-1}(M)$$

So, what you would do is have your TTP generate the three keys $k_1, k_2, k_3$ with $k_3 = k_1 \cdot k_2 \pmod {p-1}$, and you have the relation you're looking for.


Caculating Correlation for CPA attack on AES

Premise: I'm not familiar with the paper.

You probably compute 700 correlation values, one for each time sample.

For CPA you need several ($N$) traces, with different/random input but fixed key. Here each trace is made by 700 samples, each sample correspond to a different time instant.

Regarding the hypothesis, we have the HD computation which will depend on the plaintext and the key. The attacker knows the plaintext but not the key so she guesses all key values.

You put the traces in a matrix where the $N$ rows are the different acquisitions (each with a different plaintext) and the columns are the 700 time instants.
You create a second matrix with $N$ rows and 256 columns, where each entry is HD relative to the plaintext of the row and the key of the column.

Then you correlate each column of the first matrix with each column of the second matrix.
You will obtain as result 256 traces with 700 time instant, each showing the correlation of key guess $i$-th ($0<i<256$) at the $j$-th ($0<j<700$) time instant.

You don't expect all the time samples to leak in the same way, so you might have high correlation, with the correct key, only on one or few samples.


Creating a private cryptocurrency without trusted setup

The cryptocurrency you're describing does currently exist and implements, among other features, using unique Spend/View Keys in Monero (XMR). It capitalizes on a number of clever cryptographic techniques to implement a hardened total anonymization of source/destination (Ring Signatures/Stealth Addresses) and quantity (Ring Confidential Transactions/Bulletproofs).
It has also focused on maintaining a robust decentralized network via the (previously CryptoNote, GPU-optimized) RandomX PoW algorithm (CPU-optimized) that is highly ASIC-resistant, maintaining an optimal network dissemination by preventing any mining dominance by any centralized entity.
The original PoW and subsequent whitepapers can all be found at the webpage for the Monero Research Lab: https://web.getmonero.org/resources/research-lab/


Why an upside down path on the evaluation of branching program on encrypted data?

The "omitted part of this upside down algorithm" is like dynamic programming, since it

computes node values before getting to the point at which those values will be used.

Unlike my original thought, the recursive approach certainly can be better; the canonical

example of that would be using their scheme for PIR. $\:$ However, for the application your

previous question was about, their approach will definitely be better than recursion.

$P$ is just a party's input, so it certainly can be reused. $\:$ However, the resulting

ciphertext can't necessarily be run through the homomorphing process again, since the

group changes with each layer. $\:$ (That is mentioned in the top paragraph of page 16.)


Stream cipher with Diffie-Hellman and Cryptographic Hash Function?

Since the shared secret is only used for one session, assuming the hash function is a random oracle, no keystream is ever used twice.

This construction, like all stream ciphers, will cycle and produce the same key stream.

All that has to happen is $p_i$ has to equal any of the previously observed output blocks and we'll have a cycle.

If the hash is $n$-bits wide then we can expect this to occur after approximately $2^{n/2}$ blocks by the birthday paradox. The precise size of the cycle will vary from key to key.

This is kind of a problem. Some keys could have much smaller cycles than others. At its extreme, SHA-3 could have a fixed point where by SHA-3(x) = x. The cycle length would thus be one if we were unlucky enough to hit upon this value. Note that fixed points like this can absolutely occur under the random oracle model, although it is rather unlikely.

You can fix this by introducing a counter in to your state update function. Each input to the hash would be unique.

Under the random oracle model, the oracle would choose an $n$-bit hash output uniformly at random for each iteration of the state update function. This is because it never sees the same input message twice; the oracle never gets the chance to return a previously seen state.

In theory, you'd now be back to perfect secrecy. The oracle is now flipping fair coins for each bit of the message, which is analogous to the set-up we see the in the OTP.

This is just an academic point though. Obviously, in reality no hash is a random oracle. The security just reduces to the security of the underlying hash.


How does Fialka manage to have a letter encipher unto itself?

The reflector wheel on the Fialka incorporates a transistor switching circuit connecting pins 16, 18 and 24. In coding mode, a signal on pin 16 is connected via pin 18, a signal on pin 18 is connected to pin 24, and a signal on pin 24 is connected to pin 16.  In decoding mode, these paths are reversed.  This allows the Fialka to encode any letter as itself, overcoming one of the major weaknesses of the Enigma machine.


How to sign different messages using deterministic ECDSA?

Elliptic says:

  ECDSA is using deterministic k value generation as per RFC6979.

This means that every time you sign the same message you'll get the same random value used. That explains why you see the same $k$ param both times.

However, the $k$ value generation process takes the message (or the message hash) as an input. More specifically, $k$ is generated by hashing the message (hash) along with the private key. So every different message will produce a different $k$ value (apart from the negligible probability of hash collisions), and the same message will produce the same $k$ value every time it's signed.

Using the same random value with the same message is not a security risk (obviously, you just get the same signature). If you use the same random value with different messages you immediately reveal the private key, so as you note this should not be done. However, the RFC 6979 approach "ensures"  that with extremely high probability different messages will use different ks.


Zero-knowledge proof for Paillier parameters

The Poupard-Stern protocol proves knowledge of the factorization. Knowing the secret key in the Paillier encryption scheme is equivalent to knowing the factorization, hence the exact same protocol can be used to prove knowledge of the Paillier secret key.

The second part of your question, proving that the parameter $N$ is well-formed, is much, much harder. It has been studied, for example in this paper, but remains quite inefficient, since one must prove that committed numbers are prime, which is done by demonstrating in zero-knowledge that they pass all steps of a probabilistic primality test (each such step involving exponentiations, hence each such proof requires proving exponential relations between committed value, which is again relatively inefficient).


Can I simulate iterated AES-ECB with other block cipher modes?

First lets acknowledge this is a horrible hack - you really should find a way to do what you want more directly or risk code maintenance issues and likely bugs in the future.

Second, while the question isn't about your key strengthening step it seems like you should ask about the security.  There are lots of good key derivation methods out there and I don't consider iterating encryption to be a good one.

One Block CBC

Lets look at the algebraic structure of CBC on one block:

$
    \text{cbc}(v, p) = E(v \oplus p)
$

Thus if $v = 0$ $\text{cbc}(0,p) = E(0 \oplus p) = E(p)$ which is the same as ECB.

CTR

The CTR idea fail because plaintext is never part of the block encrypted by the cipher:

$
    \text{ctr}(v, p) = E(v) \oplus p
$

$
    \text{let } v = 0
$

$
    \text{ctr}(0,p) = E(0) \oplus p
$


What is the proper way to use a client nonce?

The client nonce is there to protect the client against a replay attack. Without the client nonce, an attacker could intercept the initial request for a nonce by CS, and respond with an old nonce that the server used previously. Then, the client would use that old nonce and make an API call with it, which the attacker would again intercept, and the attacker would send back the response that the true server had actually sent when the nonce was first used. To sum up, the replay attack is about making the client interact with an old ghost of the server. The client nonce allows the client to make sure that he is talking with a "fresh and alive" server.

A client nonce would not be needed if the client had a local memory large enough to recall all previously used nonces -- the kind of memory which resists across reboots, and can store all nonces for the whole duration of the shared secret life. That's rarely practical.


Fairness is, loosely speaking, the property of secure protocols that guarantees that either all honest parties will receive their output or no party will receive output. We know that this property can not be achieved for all functionalities unless when a majority of parties are honest.*

As I recall your question is a classic example of fairness not being achievable in general for two-party protocols. If we assume B could be actively corrupt, the protocol does not have fairness.

To see this note that when B gets the final bit of his output he can just abort the protocol. I.e, stop all communication with A. In this way B receives his full output but A never gets her output.

*This does NOT mean that fairness can never be achieved when there is a dishonest majority. It just means we can not get fairness for ALL functionalities in this setting.


Open Whisper Systems' own curve25519-java repository has a few test vectors in the code in android/jni/ed25519/tests/. From xeddsa_fast_test(), you get this test vector in particular:

Private key is all zeroes except byte 8, which is set to 189, and then clamped and the private key generated from there
The message is 200 bytes of zeroes
The random bytes are 64 bytes of zeroes
The resulting signature of this should be the byte sequence 11c7f3e6c4df9e8a5150e1db3b30f92de3a3b3aa438656545fa7390f4bcc7bb26c431d9e90643e4f0eaa0e9c557766fa69ada576d63dcaf2ac326c11d0b97702.

Incidentally, XEdDSA as specified has been found not to mitigate sufficiently well against differential power analysis. If the only reason why you're interested in XEdDSA is only mitigation of power-analysis attacks, you may want to look into the Internet Draft draft-mattsson-cfrg-det-sigs-with-noise-02 instead, which took into account the aforementioned findings.


There aren't many KDFs that will be faster on an AVR than PBKDF2. In your case, it's likely that the only thing you can do is find a hash which can be implemented efficiently on an ATmega2560, and implement it with as many optimizations as possible. A highly-optimized implementation of a hash algorithm is likely to improve speed significantly. That's really all you can do: Find/write a very fast AVR implementation.

If you find that PBKDF2-HMAC isn't giving you optimal performance, you could try to use a similar KDF such as S2K of the OpenPGP standard. It works by concatenating the password and salt and feeding that data into some chosen hash function. It is fed, repeating, until the configured number of bytes have been processed. See RFC 4880 § 3.7.1.3 for the specifications. It does not require any optimizations beyond optimizing the hash itself, unlike PBKDF2-HMAC. Benchmark it and see if it's good for you.


No, that won't work, and we don't even need to assume anything about the security of ISAAC to prove that.  A simple counting argument is sufficient.

Basically, the internal state of the ISAAC cipher consists of slightly over one kilobyte of data (consisting of an array of 256 32-bit integers initialized using the key/seed, plus three additional 32-bit values that don't depend on the seed).  On each call to the isaac() function, this internal state is mixed in a somewhat complicated way, and also used to compute a kilobyte of pseudorandom keystream output (also represented as an array of 256 32-bit integers).

The important part here is that, in order to compute the next kilobyte of output, you need to know the entire kilobyte of internal state.  While the output of ISAAC does not directly expose this internal state, in principle it might be possible for an attacker with unlimited computing power to reconstruct the whole internal state from the previous kilobyte (or more) of the output.  However, if you only have a single 32-bit integer of the output, then there's no way to do that even in principle — there are many, many possible internal states that could've produced those 32 bits of output, and each of those states will yield a different further keystream.

Now, there's one notable exception to this: if you know that ISAAC was seeded poorly, so that there are less than $2^{32}$ distinct possible seed values, then you can simply try each of these seeds and see which one produces the same 256th output integer that you observed.  This is because the entire ISAAC internal state is initially generated based on the seed input, so that a limited number of possible seeds implies an equally limited number of possible states.

(Note that, depending on the number of possible seeds, you might get more than one match, but probably not too many more.  In particular, for $n$ possible seeds, the expected number of coincidental extra matches is $\lambda = n/2^{32}$, and the actual number of extra matches observed is approximately Poisson distributed with rate $\lambda$.  This distribution is not specific to ISAAC in any way; any sufficiently random-looking map from $n$ possible inputs to $2^{32}$ possible observed outputs will have approximately the same statistical behavior.)


Why hash ( clear text + Secret ) instead of hash (encrpt(clear text) [ + secret ] )

There's a general principle in cryptographic protocols that every message should contain a value that depends on previous messages in the protocol. (This isn't an absolute rule, but it's usually the case.) Otherwise a man-in-the-middle might be able observe multiple runs of the protocol and combine parts of messages from different runs in unexpected ways.

I'm going by the description of the protocol on the tutorial you link to, which I think doesn't match the actual protocol (or is it SSH1? SSH2 uses the private key to sign, not to encrypt). The relevant steps are:

  3. If a public key with matching ID is found in the file, the server generates a random number and uses the public key to encrypt the number.
  4. The server sends the client this encrypted message.
  5. If the client actually has the associated private key, it will be able to decrypt the message using that key, revealing the original number.
  6. The client combines the decrypted number with the shared session key that is being used to encrypt the communication, and calculates the MD5 hash of this value.
  7. The client then sends this MD5 hash back to the server as an answer to the encrypted number message.

In step 3, the server generates a nonce and encrypts it with the public key. In step 5, the client demonstrates that it possesses the private key by using it to decrypt the nonce. In step 7, the client sends a value to the server which demonstrates that it was able to decrypt the nonce.

Now consider an active man-in-the-middle, which the protocol is supposed to defend against. The MitM waits for the legitimate client to start a session to the legitimate server, but hijacks the messages so that the legitimate client is actually talking to the MiTM, and the MitM starts its own session with the legitimate server in parallel.

The legitimate server generates a nonce $N$ (step 3) and sends the encrypted nonce $E_{\mathrm{privkey}}(M)$ to the MitM (step 4).
The MitM receives the encrypted nonce and transmits that to the legitimate client instead of generating and encrypting its own nonce. (The MitM is an attacker, so it can cheat: it doesn't have to follow the protocol correctly.)
The legitimate client receives an encrypted nonce, decrypts it and generates a hash containing it $H(N || \ldots)$ (steps 5–7).
The MitM receives $H(N || \ldots)$ and sends that to the legitimate server.

If the hash only depended on the nonce, then the MitM would be able to send a value to the server that authenticated it as a client possessing the private key. This would be a bug in the protocol.

To avoid this attack, the hash also depends on the shared session key. This shared session key is generated by a Diffie-Hellman key exchange. The DH algorithm guarantees that the resulting key depends on inputs from both sides. Therefore the session key used between the MitM and the legitimate server is different from the session key used between the legitimate client and the MitM. Since the hash calculated at step 6 includes this session key, the proof of possession expected by the server at step 7 is different from every session, which prevents a man-in-the-middle from reusing the proof of possession from another session.


What real life OpenPGP public key has the biggest amount of signatures on it?

Over time the idea of what is a strong enough key has changed and keyservers have removed keys they consider unacceptablly weak. IIRC zimmerman moved on from pgp a long time ago and I expect all his keys have been removed from keyservers due to being weak.

I was able to find a key with 230 signatures just by educated guesswork. https://pgp.cs.uu.nl/stats/587979573442684e.html . Unfortunately while that site shows data on individual keys it doesn't seem to have any ability to search/sort keys.

Data on the relationships between all keys in the "strong set" is available in "Wot files" the WoT files can be downsloaded from https://pgp.cs.uu.nl/archive/wot-0.3/ , software for working with them is available at https://pgp.cs.uu.nl/wotsap/wotsap.html . I imagine if you really want an answer to which key has the most signatures it should be possible to write code to extract it from the WoT file.

I would note that it's easy to generate a bunch of keys with random name and cross-sign them with your main key. Number of signatures on a key alone is not really a good indication of anything useful.


Counters are storing values and have usually clear, set, and increment functions. A counter can be implemented in software very easily by using an integer with enough size or using a library like Java BigInteger or Gnu/GMP for C/C++.

clear() makes the all bits zero: unsigned int counter=0
set(y) set the counter value to y : counter = y
increment() increase the current value by 1; counter++

For GCM one needs 32 bits counter and a total 128-bit for the CTR mode's counter with the 96-bit nonce.
Take a 128-bit unsigned integer and init to zero. Then GCM will use it like
$ J_0 = IV || 0^{31} ||1 $
so during the implementation, you need to take a copy of the counter, shift 32 to left, and OR with 0x01.


What is the difference between a HMAC and a hash of data?

TL;DR, an HMAC is a keyed hash of data.

A good cryptographic hash function provides one important property: collision resistance. It should be impractical to find two messages that result in the same digest.

An HMAC also provides collision resistance. But it also provides unforgeability. In order to generate an HMAC, one requires a key. If you only share this key with trusted parties, given an HMAC signature, you can be confident that only one of the trusted parties could have generated that signature.

Due to common properties of hash functions, an HMAC is not as simple as hashing the data appended to the key. This construct is vulnerable to length-extension attacks where an attacker can take a message and its HMAC signature, and use this to construct a longer message with a valid signature (thus breaking the guarantee of unforgeability).


OpenSSL: How to maintain padding from encryption after decryption?

In OpenSSL there is an -nopad option. If you don't want the OpenSSL removing the padding bytes, add the -nopad option.

openssl enc -d  -nopad -aes-128-ecb -in  encrypted.txt -K 0123456789 -v -out decrypted.txt

Note that you cannot see as C because the OpenSSL doesn't print in hex.

To see in hex you can use xxd command

 xxd -r decrypted.txt

00000000: 3132 3334 3534 3334 3837 3433 3733 3838  1234543487437388
00000010: 3431 3431 3433 3436 410a 0606 0606 0606  41414346A.......

See, the 6 06 and the plaintext was

123454348743738841414346A

Note: Note: In PKCS#7 padding with 128-bit block cipher we don't see Cs, but we have 0C, 1C,2C,3C,4C,5C,6C,7C. What you mention is PKCS#5. See the difference in What is the difference between PKCS#5 padding and PKCS#7 padding


Is it dangerous to use plaintext as IV in CBC?

As already given as partial answer in the comments, you would have to leak the second block as an IV is normally transmitted without confidentiality. You could of course retrieve it from initially decrypting the ciphertext without IV, and retrieve the first block value later on. But using an encrypted IV has got it's own vulnerabilities.

The other issue is that the IV in CBC is XOR'ed with the first block of the plaintext. Now an attacker can look at previously transmitted (initial) ciphertext blocks and see if it matches the one it is currently investigated. If they match then it knows that the result of XOR'ing the IV and plaintext matches a previous combination. This means that IV ^ P1 == IV' ^ P1'. As IV and IV' are known, this leaves you with an equation with just two variables. If more identical ciphertext blocks are found, the amount of information about the first block of plaintext increases.

There are other issues as well. You require at least two plain text blocks for your algorithm to use for instance. If there is a repeat of the first two blocks, then you will end up with an encryption of just zero's, and block 3 will become vulnerable as well.

Now it may be that your protocol is secure against these attacks, but you are using CBC without it's preconditions being satisfied, so you should then prove security of your protocol yourself.

In general, this scheme is not a good idea. It's pretty close to using a static IV instead of one that is indistinguishable from random by an attacker.


Non-repudiation and digital signature of a dishonest participant

Yes, the solution is that her public key needs to be stored in a place that is and will be accessible to Bob.

(such as in Bob's database)

I had not realized that importance of that before reading your question.


Homomorphic Encryption - Smart Vercauteren Batching

Yes, technically this is an isomorphism, so $\cong$ should be used. The isomorphism is question identifies $\theta$ with $X$.
Not quite (for the original question or your restatement).  The notation $\mathbb{Q}(\theta)$ means adjoining $\theta$, a root of $F(X)$ in the algebraic closure of $\mathbb{Q}$ (namely, $\mathbb{C}$), to $\mathbb{Q}$.  The finite field $\mathbb{F}_2$ has nothing to do with it.  (And I think $\mathbb{Q}/\mathbb{F}_2$ is meaningless, since there is no field embedding of $\mathbb{F}_2$ into $\mathbb{Q}$.)
Yes.  Such a structure is more commonly known as a number field (i.e., a finite dimensional field extension of the rationals).


Do people not care about side channel resistance?

Some implementers take notice of side-channels. An excerpt which is most relevant to your question:

  Another important point is that when timing attacks apply, they are all-encompassing: if the context is such that secret information held in a system may leak through external timing measures, then everything the system does may be subject to such leaking. This is not limited to cryptographic algorithms. Research on timing attacks tends to focus on secret keys because keys are high-value targets (a key concentrates a lot of secrecy), and cryptographers talk mostly about cryptography; however, even if all cryptographic algorithms in your system are protected against timing attacks, you are not necessarily out of trouble in that respect.

In your specific scenario, you worry about an attacker who could run his own code on the same hardware as your system, at roughly the same time as you use Shamir's Secret Sharing to split or reassemble shares for your secret data. In that setup, you ignore most "physical" side channels such as power usage, electromagnetic emissions, or noise, since exploitation of these channels requires the attacker to be in the close vicinity of the target hardware. The attacker is supposed to be remote, which limits possible side channels to what can be measured remotely or from attacker's code running on the hardware, i.e. mostly timing. Therefore, I concentrate here on timing attacks, and their countermeasures, dubbed "constant-time crypto". Practical incarnations of that attack scenario would be a multi-user Unix server (attacker is another user with a shell account), or (since this is 2017 and not 1997 any more) a cloud farm that hosts VM, and runs your VM and the attacker's VM on distinct cores of the same physical CPU.

The quoted paragraph above explains that not everything is cryptography. Indeed, you reassemble your data shares in order to have the full data in that computer, presumably in order to do something with that data. If timing attacks apply to the reassembly of shares, they should also apply to whatever you are going to do with that data. Displaying, looking for words, computing values... all of these will leak timing-based information.

In other words, if timing attacks apply to your setup, you are mostly doomed. Some specific usages will be safe: for instance, if the reassembled file is then only sent "as is" to a remote host (through some SSL or similar channel). But, in general, if you are in a timing-attack setup, then you may as well give up; or, more proactively, try to arrange for attackers not being able to run their code on your hardware.

Note that there have been lab demonstrations of cache-timing attacks from external attackers, who do not run their code on the hardware, but exercise an existing service to perform (indirectly) the same cache-measuring actions. Whether such attacks are applicable "in the wild" is still an open question.

To sum up, it may make sense not to fret too much about side-channel leaks on big systems (embedded systems are quite a different story) because such leaks would be part of a much bigger issue that should be addressed holistically.

Of course, one may also point out that it is rather unavoidable that, in a world where everybody can write three lines of code and push it on GitHub, most of that stuff will be, indeed, sloppy.


In a additive group is it hard to calculate $bg$ given $ag, g, abg$

Yes, it is equally as difficult; if we assign:

$$g' = ag$$
$$a' = a^{-1}$$
$$b' = b$$

Then the restatement of your problem is: given $g' = ag$, $a'g' = g$ and $b'g' = abg$, compute $a'b'g' = bg$, which is exactly the ECDH problem.

Now, this assumes that $a$ has an inverse; this is not a problem if the curve order is a prime, and is easy to work around if the curve order is a prime times a small cofactor.


Hamming Distance vs. Index of Coincidence

The Hamming distance is more effective when you suspect that the plaintext has been XORed with some repeating keystream.  That's because XOR works at a bit level, as does the Hamming distance.

The Index of Coincidence is more effective when you suspect that the plaintext has been combined with some repeating keystream, where the combiner works character-by-character instead of bit-by-bit.  For instance, the IoC will be more effective for a Vigenere cipher, or for a repeating-key polyalphabetic cipher.  This is because those ciphers transform individual characters of the plaintext as a unit (not individual bits), and the IoC works at the character level.

If you like, you can think of the Hamming distance technique as effectively applying the Index of Coincidence at the bit level: the Hamming distance is effectively a variant of the IoC that works at the bit level, and that is especially effective when the combiner is the bitwise XOR operation.  Therefore, if you know that the plaintext is combined with some repeating keystream using some bitwise operation (such as XOR), then you might use the Hamming distance (effective, applying the IoC at the bit level instead of the character level).

Of course, you can always apply both and see which works better on your particular cipher -- but the above discussion tells you which method you should expect will work better in any given circumstance, and why.


Should I PGP encrypt using a publickey intended only for Certify?

Encrypting with a DSA key—as the master key is—doesn't make sense.  It appears that someone neglected to put the encryption usage flags on the Elgamal encryption subkey, which would be the obvious one to use.


Signal Protocol Header key encryption initialization vector

The security contract for AES-CBC is that the initialization vector must be uniform random and unpredictable in advance—mere uniqueness is not enough (nor even necessary).

It is safe to choose the IV as a pseudorandom function of a unique nonce, or even as a pseudorandom permutation of a unique nonce, which the sender and receiver can agree on—e.g., they could choose it to be a message counter, if they are both capable of counting—without sending any explicit IV over the wire.  Indeed, you could even use a message counter encrypted with AES under the same key, as long as the attacker has no control over the counter.

It is not safe to choose the IV as anything that an attacker can predict in advance, like a public key previously sent over the wire and a predictable counter.


Squaring the coefficients in homomorphic encryption

In the Fan-Vercauteren scheme, ciphertexts are composed of 2 polynomials, call them $ct_0$ and $ct_1$.
Although homomorphic addition is really simple (add the two parts independently), the same cannot be said for multiplication. As you noticed, simply multiplying the polynomials won't give you the desired result.
The homomorphic multiplication is composed of 2 steps.
First, you compute an intermediary ciphertext (it is not a real ciphertext because it's composed of 3 elements and not 2):
$$\frac{t}{q}ct_0ct'_0, \;\; \frac{t}{q}(ct_0ct'_1+ct_1ct'_0), \;\; \frac{t}{q}ct_1ct'_1$$ all of them rounded and taken modulo q. This intermediate can be obtained with the SEAL library using Evaluator::multiply.
You can use only this operation and keep your ciphertext size growing, but at some point, it would be more efficient to relinearize.
This operation is used to go back to a ciphertext containing only 2 elements, and can be obtained with the SEAL library using Evaluator::relinearize (it needs a key as a second argument that can be generated using KeyGenerator::generate_evaluation_keys.

Now in order to square an element, you just have to multiply it by itself, but using the correct multiplication operation instead of the naive one.

For more details, you can have a look at this documentation.


If one expands the discussion to include LWE-type schemes, isn't Module-LWE naturally a "non-commutative" hardness assumption which has practical applications? For example, the Kyber NIST PQC candidate is an MLWE scheme, and is a round 3 finalist.
In general though, I mostly see lattices over "exotic" (at least more so than things like RLWE/MLWE) algebraic structures discussed by coding theorists (two specific examples are Fredrique Oggier and Cong Ling). As there seems to be a larger theoretical basis of research on "that side" of things, it might be easier to search for practical applications.


Which cipher text is easiest to guess the plaintext?

You're right.

For a substitution cipher the huge size of the keyspace is quite irrelevant in terms of security: it does not change the frequencies of letters, just maps them to other letters. So you you can go from the most common letter and map that, then the 2. most common, etc. And after maybe the 10 most common letters you can use a dictionary with English words and the partially mapped words to exclude other possibilities to get the remaining mappings. "Security" is barely better than a Caesar cipher.

For A5/1 it took over 10 years to be broken, so in contrast it is is not trivially broken by modern computers, like basically any classical cipher.

I guess the point of the exercise is: A large keyspace does not mean, the cipher is secure.


How is a sponge construction better than cycling the output of a hash back to the input?

why not have $r$ be the whole block?

Because you'd essentially have no security.

In the absorbing phase, the attacker could set the intermediate state to whatever he wants.  For example, if the current state is $c_{n-1}$ and the attacker wants the next state to be $t$, he computes $p_n = c_{n-1} \oplus f^{-1}(t)$; this allows a trivial preimage attack.  And, even if $f$ wasn't invertible, this would still allow a trivial second preimage attack.
In the squeezing phase, if the attacker knows the value $z_0$, he could trivially compute the rest of the hash $z_1, z_2, ...$


How can we evaluate a polynomials in a group instead of a field? (verifiable secret sharing on elliptic curves)

It is correct to me. Polynomial is not evaluated in the elliptic curve group $G$, but in $F_q$ (where $q$ is the order of $G$), which is a field because $q$ is a prime number.

To be clearer, I add brackets to the equation you gave: $$X_i = \prod_{j=0}^{t-1} (C_j)^{{i}^j} = \prod_{j=0}^{t-1} (g^{\alpha_j})^{ i^j}= (g)^{ \sum^{t-1}_{j=0} \alpha_j i^j}$$ You can see the polynomial is evaluated in the exponent, that why it is in $F_q$.

Maybe it is easier to see if using the Elliptic curve notation (let $P$ be a generator of the EC group $G$, i.e. $g$ in the above equation):

$$X_i = \sum_{j=0}^{t-1} ({i}^j\cdot C_j) = \sum_{j=0}^{t-1} ({i}^j\cdot a_j\cdot P)= (\sum_{j=0}^{t-1} a_j\cdot {i}^j )\cdot P$$


Is Wiener's attack on RSA extendable to larger keys with low hamming weight?

First, you have a typo in your question. Wiener's attack works if $\log(d) < 0.25 \log(N)$.
This is not the best possible attack. "Boneh and Durfee" improved the result to $\log(d) < 0.292 \log(N)$.

I'm not aware of any better result, but that does not mean such results do not exist.
In particular, it is quite unclear whether it would help an attacker to know that the Hamming weight of the private key is small.

Generally, it is very risky to use these corner cutting techniques. There are countless proposals for speeding up RSA by generating the private key in a particular way that already.

A good overview over the topic is Alexander May's thesis. This thesis is a few years old, but does nicely show what kind of attacks are possible, and more importantly how complex this subject is.

I would recommend not to use any RSA implemenation that tries to optimize performance by fiddling with the secret key.


It looks like it can be solved quickly using a branch-and-bound procedure, assuming that the number of elements in the permutation is not excessively large.

(Notation: I'll use capital letters to specify permutations, and lower case letters to specify individual elements of the permutation); in addition, I'll take the convention that $XY$ means "apply the permutation $X$ to the elements, and then apply the permutation $Y$)

The algorithm is straight-forward; we know that $XY = ZX$, so:

We pick an arbitrary element of the permutation $a$ and assume that $X(a) = b$ (where $b$ is a previously output of $X$).  We then can deduce the value $XY(a) = d$ (where $d = Y(b)$).  In addition, we have $Z(a) = c$ (for some element $c$), and so we can then deduce $X(c) = d$.

Assuming that $c, d$ are previously unknown inputs/outputs of $X$, we reiterate the same logic, which will give us another pair $X(e) = f$.

We keep on doing this until it gives us a pair that we've seen before, or it gives an inconsistent pair (that is, it assigned the same $X(g)$ value to two different outputs, or it gives us a set $g \ne h, i$ with $X(g) = X(h) = i$

If it gives us an inconsistent pair, we drop back to the previous assumption that $X(a) = b$, and modify $b$, and restart our computation from there.

If it gives us a pair that we've seen before, and there are still unassigned inputs/outputs to $X$, we restart at the beginning, arbitrarily selecting a previously unassigned input/output pair.

This won't give a unique value of $X$; that's because there are multiple solutions, and this will pick one arbitrarily.

Update: I just wrote a quick (and fairly suboptimal) C program to do this; it could find a conjugate (where one existed) given two permutations over 10,000 elements in under a second...


First things first, I would not have described BearSSL as being "bignum-free". However, it is true that it does not have a generic implementation of big integers; what it contains is a generic implementation (actually several) of big modular integers. And it matters.

About low-level multiplications

Software libraries run on some hardware and cannot use anything else than what the hardware offers. Regarding multiplications, a common CPU will offer a 32-bit multiplication with a 64-bit result. For instance, the x86 line of CPU has an assembly opcode called mul that multiplies two 32-bit unsigned values (one in the eax register, the other in a register passed as parameter) and yields a 64-bit result, split into two 32-bit halves in eax and edx. When writing C code, you usually obtain a result of the same size as the operand, i.e. if you multiply two uint32_t values, you get a uint32_t result; to obtain the full 64-bit result, you need to use some casts into uint64_t. When BearSSL was first released, this 32×32→64 multiplication was the largest that the implementation was using.

Some architectures do not offer a 32×32→64 opcode. In particular, the ARM Cortex M0 and M0+ have an efficient 32×32→32 opcode, but a 32×32→64 multiplication must use a software routine that is considerably slower (we are talking about 1 cycle vs 40 cycles here) and also often non-constant-time. Some other have a 32×32→64 opcode, but it is not constant-time (e.g. ARM Cortex M3). This is why BearSSL also offers implementations that use only 16×16→32 multiplications (these are codenamed "i15" in the BearSSL API).

More recently, I added some code called "i62" which leverages the 64×64→128 opcodes that are available on some big architectures, in particular x86 in 64-bit mode. This requires using some compiler-specific extensions, because (in general) there is no uint128_t type made available (see here for the relevant source code; this is done only for modular exponentiations, as used in RSA).

About generic bignum code

Many cryptographic libraries include a generic "big integer" implementation: this is a set of memory structures and functions that can represent and perform arithmetic operations on integers which are not a priori limited in length. In OpenSSL, this is called BIGNUM (or "BN"). Internally, each such big integer is a structure that references an array that contains the integer contents, split into elementary "limbs" (in the same way that when you write an integer in decimal, you represent it as a sequence of digits); other structure elements contain the actual integer length and relevant memory management information.

Writing a generic big integer library is a natural way of doing things: a good software engineer thinks top-down and writes code bottom-up. Thus, since many asymmetric cryptographic algorithms are expressed over large integers (e.g. RSA, DSA, ECC...), that engineer will start by writing a good, reliable big integer library, then use it to implement the relevant algorithms. As a second phase, for pure performance reasons, some of the most expensive operations in the said algorithms will be reimplemented with dedicated code (that's how OpenSSL now has dedicated assembly code with AVX2 opcodes that handles, specifically, the modular exponentiations in RSA for RSA keys of length exactly 2048 bits). Also, when implementing cryptography in some languages, a big integer library is already there and ready to be used (e.g. Java's java.math.BigInteger).

Now, BearSSL does not follow that road, and there is a reason. BearSSL does not include a generic "big integer" library. It has something which somewhat looks like it, but really implements operations on modular integers, i.e. integers considered modulo a given (odd) integer. The functions are not part of the public API (this is for internal use) but are documented here. Implementation is in the src/int/ directory.

The underlying reason is the quest for constant-time code, so as not to leak information through timing-based side channel attacks, in particular cache attacks. To really defeat such attacks, the implementation must use a memory access pattern that does not depend on secret information. However, a generic big integer implementation cannot be constant-time, because values are allocated in buffers which are dynamically sized, depending on the represented integer; therefore, an attacker who can observe the memory access pattern of some code will be able to notice when an integer value is "short" or "long".

To follow a strict constant-time discipline in BearSSL, a modular integer is handled in an array whose length matches that of the modulus, not that of the value itself, and all array slots are always accessed, even in cases where some contains only zeros. Internally, that concept is described as "announced bit length": a big integer structure, in its header, states a bit length which is that of the modulus, and all operation loops work on that bit length, not on any length inferred from the value (the big integer "structure" is actually a simple array of words, and the "header" is the first word in that array).

It shall be noted that usual cryptographic libraries like OpenSSL have a long history, which began way before cache attacks were invented; moreover, their "big integer" library is often part of the public API, and thus they cannot simply remove it without breaking compatibility with existing applications. BearSSL is relatively recent (I started it in 2015), and thus I could design its structure and API with full knowledge of cache attacks, hence the lack of generic big integer code, and also the fact that the code for modular integers is not part of the public API (so that I may change things later on, if necessary).


Is my pseudo-random initialization vector secure?

Just use the build in crypto PRNG of your operating system or framework.

C# / .net: RNGCryptoServiceProvider Class
Java: SecureRandom Class
Linux: /dev/urandom
Win32 API: CryptGenRandom function

date/time might be enough for modes which only require uniqueness, but if you generate two IVs in quick succession(within 16ms or so) or if the clock is changed. It's still an unnecessary risk.

date/time is certainly not enough for modes where an unpredictable IV is required, such as some uses of CBC.


Using 3DES decryption to get a specific result

I want to apply 3DES decryption on key and data to get a specific result. Is this possible in theory?

Sure. 3DES is a functionally correct encryption scheme for any fixed key, so for any message there exists a(t least one) corresponding ciphertext value.

So if you want to have a specific decryption result $m$ using a specific key $k$, you simply choose the ciphertext $c$ as $c=E_k(m)$ and by correctness $D_k(c)=D_k(E_k(m))=m$.


Would requiring reciprocal signatures create a stronger Web of Trust?

Would we also need some additional options/messages in GnuPG to make it clear when you might be looking at an "unauthenticated" signature?

Hopefully I'm not stating the obvious.

OpenPGP does not trust keys simply because lots of people have signed them. You must "set ownertrust" for the keys you have before they will be used in Web of Trust calculations.

This related answer has some good information about how the Web of Trust is calculated.

  He is effectively forging a web of trust.

Nope.

If you haven't trusted Michael Vario's key, then you have nothing to worry about. It's just spam.

If somebody you know is verifying a key by any method other than Web or Trust or verifying the fingerprint with the owner, they are using PGP wrong. End of story.

  It occurred to me that if the public key servers could be asked to return public keys with only those signatures that are reciprocal we would perhaps have a more realistic picture of who trusts who.

Perhaps this would be useful, but I personally see it as unnecessary. PGP is complex enough as it is :)

Sidenote: If you trust a key enough for the purposes you are using it for but you don't trust it enough to "put your name on", you can perform a "local signing" that will be considered for Web of Trust calculations that won't be exported to any keyservers.


Use the exponential variant of ElGamal, where the plaintext is encoded in the exponent. Elliptic curve ElGamal is fine. In fact, any public key cryptosystem which allows raising ciphertexts to a power such that this operation corresponds homomorphically to multiplication for the plaintext.

Your commitments are $c_x = \mathsf{E}(x)$; $c_y = \mathsf{E}(y)$; and $c_z = \mathsf{E}(z)$. Additionally, you must commit to an encryption of one: $c_1 = \mathsf{E}(1)$, and prove that it is an encryption of one using a Schnorr proof.

Next, use the Chaum-Pedersen proof of equivalent discrete logarithms to prove the following relation: dlog$_{c_1}c_y = $ dlog$_{c_x}c_z$.

Schnorr proof:

Public knowledge: $a, b$

Private knowledge for $\mathcal{P}$: $s$

Claim: $a = b^s$

$\begin{matrix}
\mathcal{P} & & \mathcal{V} \\
u \xleftarrow{\$} \mathbb{Z}_q & & \\
v \leftarrow b^u & & \\
 & \xrightarrow{\quad v \quad} & \\
 & & e \xleftarrow{\$} \mathbb{Z}_q \\
 & \xleftarrow{\quad e \quad} & \\
r \leftarrow se + u \mod q & & \\
 & \xleftarrow{\quad r \quad} & \\
 & & b^r \stackrel{?}{=} a^ev
\end{matrix}$

The Chaum-Pedersen proof is very similar:

Public knowledge: $a_1, a_2, b_1, b_2$

Private knowledge for $\mathcal{P}$: $s$

Claim: $s = $ dlog$_{b_1}a_1 = $ dlog$_{b_2}a_2$

$\begin{matrix}
\mathcal{P} & & \mathcal{V} \\
u \xleftarrow{\$} \mathbb{Z}_q & & \\
v_1 \leftarrow b_1^u & & \\
v_2 \leftarrow b_2^u & & \\
 & \xrightarrow{\quad v_1,v_2 \quad} & \\
 & & e \xleftarrow{\$} \mathbb{Z}_q \\
 & \xleftarrow{\quad e \quad} & \\
r \leftarrow se + u \mod q & & \\
 & \xleftarrow{\quad r \quad} & \\
 & & b_1^r \stackrel{?}{=} a_1^ev_1 \\
 & & b_2^r \stackrel{?}{=} a_2^ev_2 \\
\end{matrix}$

At this point, I thought my answer was complete, but the questioner correctly notes: "This is an excellent start, but it proves that $xy \equiv z \pmod q$, rather than that $xy=z$. I think if you choose $q$ to be $>2k$ bits long, and combine it with a range proof of the size of $x,y,z$, though, this might work."

It is nice that you specify that $x, y$ and $z$ are in $[0,2^k]$, because that makes the range proof a little easier. In order to prove this range of $x$ (same for $y$ and $z$), do the following:

Commit to $k$ bits of $x$, i.e.: send $\mathsf{E}(x_i)$ to the verifier, where $x_i$ is the $i$th bit of x.
Prove the commitments are encryptions of either 1 or 0.
The verifier can aggregate the bits homomorphically: $\mathsf{E}(x) = \prod_i \mathsf{E}(x_i)^{2^i}$. Use this as the commitment of $x$.

It remains to be shown how to prove that an encryption is an encryption either of 1 or else of 0. This can be done using the CDS proof linking technique (link).

First, note that in the ElGamal cryptosystem, it is easy to prove that an encryption $\mathsf{E}(a)$ encrypts a plaintext $a$. The encryption is given by $\mathsf{E}(a) = (g^y, g^{a+xy})$. Divide $g^a$ out of the second value and then produce a (Chaum-Pedersen) proof that dlog$_g g^y = $ dlog$_{g^x}g^{xy}$.

Second, note that it is also easy to falsely "prove" that an encryption $\mathsf{E}(a)$ encrypts a different plaintext $b$, provided that you control the challenge $e$ sent by the challenger. The claim to be proved is dlog$_g g^y = $ dlog$_{g^x}g^{-b+a+xy}$. Generate the proof transcript as follows (let $a_1$ correspond to $g^y$, $b_1$ to $g$, $a_2$ to $g^{xy}$ and $b_2$ to $g^x$): $e, r \xleftarrow{\$} \mathbb{Z}_q$; $v_1 \leftarrow b_1^ra_1^{-e}$; $v_2 \leftarrow b_2^ra_2^{-e}$.

The central idea of the CDS technique is to generate two proof transcripts, one of which is made interactively with the verifier and the other of which was generated beforehand. This is done in such a way that the verifier cannot tell which one of the two proofs was interactively made and which one was generated earlier. In particular,

The prover generates a proof transcript $T_f$ of the false claim: $T_f = (c_f,e_f,t_f)$, and a first message of the true claim: $c_t$.
The prover sends the two first messages to the verifier: $\mathcal{P} \xrightarrow{\quad c_f, c_t \quad} \mathcal{V}$.
The verifier chooses a random challenge $e \xleftarrow{\$} \mathbb{Z}_q$ and sends it to the prover: $\mathcal{P} \xleftarrow{\quad e \quad} \mathcal{V}$.
The prover interpolates on the line defined by the two points $(0,e), (1,e_f)$ and evaluates it in $2$ to obtain $e_t$.
The prover completes the transcript $T_t$ of the proof of the true claim using $e_t$.
The prover sends both transcripts to the verifier: $\mathcal{P} \xrightarrow{\quad T_f, T_t \quad} \mathcal{V}$.
The verifier verifies the proof transcripts and verifies that $(0,e), (1,e_f), (2,e_t)$ are on the same straight line.

The reason this technique works is because the prover can prove only one of the claims. Having committed to the false proof, he has no degrees of freedom left to choose his challenge for the true proof. Thus, the verifier knows that at least one of the transcripts was produced interactively. Obviously, the order of $T_t$ and $T_f$ must be random because otherwise the verifier can easily tell which one is true and which one is false.


How come “short” (eg 80 bit) MACs are regarded to be safe?

But for the second, I don´t know how to start.

I won't give you the answer (this is homework; you won't learn as much if I just give you the answer); I will give you hints.

  It’s not given how the MAC is calculated.

No, but for this question, we assume that the attacker knows what the MAC is; he just doesn't know the key.  We also assume that he knows the correct MAC for a number of different messages (actually, we assume that the attacker can ask for a MAC for messages of his choosing; that ability won't help you in this attack).

What does that mean?  Well, it means that, for the purpose of this question, we treat the MAC as a black box; the attacker can (to his heart's content, up to the limits of the computational resources he has on hand) generate keys and messages and compute what the MAC would be for that key.

So, with those capabilities, our attacker's job is to get a (message, MAC) pair accepted, for a message he hasn't seen (he's not allowed to submit one of the (message, MAC) pairs he's already been given).  How can he do that?

Hint: there are two basic ways the attacker can proceed; one involves his use of the black box, and one does not.


Using CBC with a fixed IV and a random first plaintext block

The security of that approach is equivalent to that of normal CBC.

Your scheme with first plaintext block $IV^\prime$ is clearly identical to normal CBC with $IV=AES(IV^\prime)$. Since a block cipher is a permutation over a block, a uniformly random first plaintext block will lead to a uniformly random IV for normal CBC.

A ciphertext produced with your scheme is of the same nature as with plain CBC. i.e. you can decrypt a normal CBC ciphertext with your algo, and you can decrypt a ciphertext produced by your algo with normal CBC.

The only downside of your scheme is that it costs one additional AES invocation per message. No difference in ciphertext size, and no CPU cost beyond that single call.

One interesting question is what happens with IVs that are unique, but not unpredictable. I suspect your scheme is secure in such a situation, unlike normal CBC. But I don't have a proof for that.


Well, I'll assume that we'll use the same mapping between letters and integers both to translate the plaintext into integers (to be matrix multipled), and the integers (after the matrix multiply) back into ciphertext.  And, we don't know that mapping, the key matrix $K$, and possibly the value of $n$.

If so, the obvious place to start is to attempt to solve this $\bmod \ 2$.  The key matrix $K$ consists of integers modulo 26; because 2 is a divisor of 26, it can be treated as if it consists of integers modulo 2.  The mapping assigns 13 characters to even integers and 13 characters to odd integers; there are $\binom{26}{13} = 10,400,600$ possibilities.  So, what we (actually, a computer, this is a bit much for hand computation) can do is scan through all 10 million possibilities (and through the reasonable values of $n$, if we don't know that), and check if that mapping to even/odd characters is consistent with the known plaintext/ciphertext.

The result of this will be the lsbits of the mapping (which are the 13 even characters, and which are the odd characters), the lsbits of the elements of $K$, and the value of $n$.

The next obvious thing to attack, if we have enough plaintext, is to recover the mapping of the even characters.  There are $13! = 6,227,020,800$ such possible mappings; if we can find (say) $n+1$ blocks that consist of only even characters (and both the plaintext and the ciphertext blocks will consist of even characters; we know this because the mapping is consistent $\bmod \ 2$), then we can scan through the 13! possible mappings, and see if each such mapping is consistent with all $n+1$ plaintext/ciphertext pairs.  If $n=5$, then we expect to be able to find 6 such blocks if we have at least 1200 characters of known plaintext; not unreasonable.

Once we have that, that gives us the value of $K$, and the mapping for the even characters.  With that, deducing the mapping of the odd characters is straight-forward.


How to meter and limit number of files encrypted?

I believe the concept you're looking for is a cryptographical hash.  This is a function that takes a (potentially) long input, produces a short (fixed length) output, and for which it is impractical to find two different inputs that generate the same output.  It is a fixed function; anyone (including your customer) can generate a hash for any input.

How it would work is:

The customer would generate the hash of their file, and send it to you
You would take this hash, and generate a key (or signature) for that hash, and send it to the black box
The black box would take the signature and the file, compute the hash of the file, and verify that the hash corresponds to the signature.  If so, it'll go ahead and process the file (and produce the output).

One common cryptographical hash function is SHA-256; it has an output which is 256 bits (64 hex digits long); it needs to be that long to avoid attacks where someone computes a long series of hashes, and looks for two different inputs that happen to generate the same hash.

Alternatively, if the limit on the number of times that a black box can be used isn't too large, the black box could just compute and store the hashes of the input files itself.  In this case, if the customer submits an input twice, the black box will compute the same hash value, see that it's already on its list, and realize that it's recomputing an input.


Can a properly implemented ed25519 private key with public underlying data be cracked?

No, this does not weaken ed25519 in any way. Known plaintext will not have any effect on a signature algorithm, if it did it would make that algorithm completely useless.


Will X9.31 remain a secure & acceptable deterministic random generator beyond 2015?

X9.31-based PRNGs as used in current practice (including in the Botan library) tend to be extensions of the generator of ANSI X9.31-1998 appendix A.2.4 (which designated purpose is as a submodule of a prime generator for RSA keys). This really is the PRNG of ANSI X9.17-1985 Appendix C (which designated purpose is generating DES keys), also described in modern form in section 5.3.1 of the HAC. This generator has a sound and time-tested structure; however I know no theoretical argument reducing security to that of the underlying block cipher. Update: and, as pointed by Gilles in another answer, it lacks backtracking resistance: past output can be deduced from the current state, which is a concern in some applications where the state is kept for extended period, rather than safely disposed of after use, and could get compromised.

This original generator, designated ANSI931_TDES2 in NIST test vectors, does show its age in the use of Triple-DES with two keys, which has limited 64-bit block size, 112-bit key entropy, theoretical vulnerability to meet-in-the-middle variants, and poor suitability for software implementation, with in particular risk of timing attacks on CPUs with caches, and other side-channel attacks. All this is reason enough for ANSI931_TDES2 to be abandoned with a deadline at the end of 2015, per NIST SP800-131A Table 3.

Four common extensions have been defined in NIST-Recommended Random Number Generator Based on ANSI X9.31 Appendix A.2.4 Using the 3-Key Triple DES and AES Algorithms (2005). ANSI931_TDES3 just widens the key to an effective key size of 168 bits. ANSI931_AES128, ANSI931_AES192, ANSI931_AES256 use AES, with the corresponding key size; and make all variable data 128-bit wide. As far as I can tell these generators are in an administrative state of limbo: neither explicitly deprecated, nor with recent re-approval. I sure would not want to use ANSI931_TDES3 for any new development.

It seems inconceivable to me that a practically useful cryptanalytic attack of ANSI931_AES256 (the variant claimed to be used in the Botan library) could emerge within a human lifetime, assuming an adversary knowing nothing about secret key and primary seed material chosen uniformly at random, trying to predict some of the output, knowing all other external data (other output and auxiliary seed material), and not in a position to conduct side-channel or fault injection attacks on the internal state of the generator (Update: including as left after the PRNG's intended use). I base this assessment on the lack of published attack on the original PRNG after 30 years of exposure, and the dramatic security boost given by the widening of key and state.

Note: After I dug ANSI X9.31-1998 from my chest of purchased standards, I intended to make this answer a detailed analysis of the birth, life and fall of the 3 generators in appendix A, and their descendants. This turned out to be inextricably difficult, because the algorithm in appendix A.2.1 as written is dead wrong in step 4e where the output is supposedly generated, and there's no test vectors as a lifebuoy; also I could not determine which of it or FIPS 186-1 Appendix 3.1 (nearly identical except for the defective step) predates the other.


How can one calculate the estimated RSA key life based on Moore's law?

It is hard. Main problem is that RSA key breaking relies on integer factorization, for which the most efficient (known) algorithms use CPU but also RAM, with constraints on parallel computation. Moore's law is already a crude approximation of how CPU power evolves over time for a given budget; it fails to take into account memory size and latency (two distinct things).

In fact, Moore's law, as expressed by Gordon Moore, is about transistor density, which does not equate with performance; and Moore himself changed it occasionally. The version that was fashionable about 12 years ago was: "every three years, one can put four times as many transistors in a given area, and clock that twice faster". This translates to an increase in computational power of 1 bit per year when breaking symmetric algorithms with FPGA or ASIC; but for general purpose computers, this is more like a double in power every 18 months, because register size does not increase as fast, and even when registers grow, the data elements we put in them do not. Also, over the last decade, clock rate of CPU has more or less stabilized, so Moore's law can be maintained only through parallelism -- multiple cores. But not all algorithms are amenable to easy parallelism, in particular the big matrix reduction which is the last step of General Number Field Sieve, the current best algorithm for breaking RSA. That matrix reduction appears to be the bottleneck for keys longer than the current record (768 bits).

Read section 6 of this report for a discussion and pointers on the subject. All see this site for estimates computed by various organizations, and even more pointers.


If you have the values of all nodes you can always easily recover the plaintext in MPC.


Relation between short and «regular» Schnorr signature

@Maher's comments guided me to understanding.
To prove security of short Schnorr signature from security of «regular» Schnorr signature with the same hash $H$, we hypothesizes a PPT algorithm $\mathcal A$ that breaks short Schnorr signature, and use it to build algorithm $\mathcal A'$ that breaks regular Schnorr signature, as follows.
$\mathcal A'$ does as $\mathcal A$, except:

Whenever $\mathcal A$ requests a signature: $\mathcal A'$ requests a signature for the same message $m$ from the regular Schnorr signature oracle, gets a regular signature $(u_t,\alpha_z)$, turns it into a short signature $(H(m,u_t),\alpha_z)$ by applying $u_t\mapsto H(u_t,m)$ to the first component of the signature, and uses that for whatever $\mathcal A$ does.
When and if $\mathcal A$ outputs a forgery: $\mathcal A'$ turns that short signature forgery into a regular signature forgery by applying $c\mapsto g^{\alpha_z}\,u^{-c}$ to the first component of the forgery, using only knowledge of public key $u$ and the group parameters.

Algorithm $\mathcal A'$ remains PPT, and breaks regular Schnorr signature with the same probability as $\mathcal A$; only extra cost are more queries to the random oracle performing the hash, and the final computation for the forgery.

What Boneh and Shoup's 19.2.3 leaves unclear to me is how it's justified

It will be sufficient to work with 128-bit challenges.

that is why $H$ with output much narrower that the group order will do in regular Schnorr signature.


Is it possible to construct a compression function that works exactly as MD5's CF but is much easier to compute?

Not that we know of.

Although we have no proof, there is still a strong belief that MD5 represents a one-way hash. It is broken, but that doesn't mean we can reverse it (or the compression function that it is based on).

Similarly, we don't know a faster way to compute it (in the algorithmic sense) but we cannot proof that there isn't a faster "representation".

One of the things to consider here is P versus NP. As long as this remains unsolved we don't know if P = NP could hold, which would have interesting consequences.


If the question is "if I just had MD5 as my sole cryptographical primitive, could I use it to encrypt", well, the answer is yes, you can.  Then are a number of standard block cipher modes that don't assume invertability of the block cipher, and hence would work just find if you plopped MD5 (or rather, a keyed MD5, where you ask MD5 to hash both the input block and some keying data) right there.  Examples of such modes are CFB, OFB and Counter mode.  We don't do this in practice, both because MD5 hasn't been studied in such a mode (because the assumptions we're making on MD5 aren't the standard assumptions of hash functions, but ones concerning a large number of hashes from related images), so no one could say that it is secure), and because it would be rather slow.

On the other hand, your question would appear to be "if I have a database that includes an MD5 hash of some data, could I reconstruct what the original data was".  Well, we don't normally call that "encryption" (because there's no way to undo that operation).  And, if that is your question, the answer is no (unless you can guess what that data is, and verify it by doing an MD5 on your guess).  Even if the original data was short enough that there is unlikely to be another string that short that hashes to the same value, there is no known way (other than brute force) to find MD5 preimages, much less a specific MD5 preimage.


Order of letters on 3-rd rotor: Enigma III

OK, so first you need to index the alphabet. So let's say that A=0 and Z=25 - a zero based index - as we need to perform modular arithmetic.

Lets reference the letters of the first wheel with index $i_1$ and the letters of the second wheel $i_2$. Then $i_2$is simply $i_1+20 \mod 26$. Note that the second wheel moves in the other direction as the first wheel, but that the alphabet is reversed to counter clockwise.

The third wheel has a repeating pattern of three characters: "BAC EDF ...". Here the arrow is to the side. The letters are now clockwise again.

Let's simplify the third wheel so that A is converted to B, B becomes A and C stays C. So index 0 becomes 1, index 1 becomes 0 and index 2 stays 2. The offset from the start of each set of three characters can then be written as $k_3 = (-j_3 + 1) \bmod 3$ for all mappings. To calculate the offset in the simplified wheel we have to add the start of the set: $l_3 = \lfloor j_3 / 3 \rfloor \cdot 3$.

Finally, we should undo the given simplification: a quick check will find that the alphabet has shifted 16 characters.

So the answer becomes $$i_3 = k_3 + l_3 = (-j_3 + 1) \bmod 3 + \lfloor j_3 / 3 \rfloor \cdot 3 \mod 26$$ where $$j_3 = i_2 + 16 \mod 26$$

Obviously it is much easier to simply write down which character comes up at the other wheel for each character of the alphabet. Then you only need to shift up to 25 places for each setting of the wheel.

Note that it is possible to change the order of the wheels and how the wheels are positions in relation to each other. If these changes could not be made it would be easy simply to change the to right hand wheels with a single wheel (which would have the same formula as wheel 3, but with constant 10 as $20 + 16 \bmod 26 = 10$).


Tweakable encryption algorithms vs Key wrapping

Key wrapping and tweakable encryption are actually quite different topics.
Key wrapping is more commonly related to keys forage and key archive.

Key wrapping

This is fancy terminology for encryption key with another key.
In key wrapping you have a master key that is used to protect one or more keys. It is generally impossible for (computationally constrained adversary) to decrypt wrapped key with no access to appropriate decryption key.

There are key wrapping mechanisms used with asymmetric cryptography, i.e. encryption and decryption with different key (such as RSA-OAEP), and symmetric cryptography, such as AES-KW. Many key wrapping algorithms provide some level of integrity/authenticity protection in addition to encryption.

For purposes of key storage and key archive, key wrapping is very often used.

Key derivation

(As introduction towards tweakable encryption). Key derivation is kind of counterpart of key wrapping. The master key is not used to protect wrapped key, but instead a key derivation algorithm is used to produce other keys from master key. The algorithm may, for instance, generate the keys based on purpose (as identified by "Label") and possibly, other fields related to context. Key derivation can be useful when many keys are needed, but it is not desirable to store all the keys, but only store the master key. (Thus, for key storage, this algorithm is not ideal.)

Tweakable encryption

In some fields, most notably Full Disk Encryption, it is would be desirable to use very large number of cryptographic keys, for instance, to use different cryptographic key per each sector. Conceptually, this is very close to using key derivation to derive per sector keys. Unlike key wrapping, in tweakable encryption the per sector keys are not (usually) stored anywhere.

The tweakable encryption algorithms have been usually implemented with optimization goal that it is very lightweight to change one parameter (tweak).
For purpose of key storage and key archive, in many cases, current tweakable encryption algorithms are of little use. Tweakable encryption (for instance XTS-AES), is mainly intended to protect (lower value) bulk data, in situations where data size extension to allow for integrity/authenticity checking is not an option.


Are zero-knowledge proofs quantum-resistant?

There is no generic answer to this question. Zero-knowledge proof (ZKP) systems can be post-quantum secure, but they need not be. It all depends on the cryptography on which the security of the ZKP rests.
There exist ZKPs that only use collision-resistant hash functions and hence are plausibly post-quantum secure. The most well-known examples are those using the FRI protocol: Aurora, Fractal, and zk-Starks [*].
Other notable ZKPs like Bulletproofs or Groth16 rely on cryptographic assumptions (e.g. hardness of discrete log in elliptic curve groups) for which it is known they would be vulnerable to quantum attacks, if such attacks became practical.
[*] "zk-STARK" refers both to a security definition and to a particular family of FRI-based proof systems that satisfies it. The security definition does not mention post-quantum security, so it is the latter that is meant here.


Difference between Pedersen commitment and commitment based on ElGamal

The main difference is that Pedersen commitments are unconditionally hiding, as given $g^mh^r$ represents an information theoretic hiding commitment, i.e., even an unbounded adversary will not be able to figure out $m$.

In exponential ElGamal encryption, since you publish $(g^r,g^mh^r)$, this so obtained commitment is no longer unconditionally hiding, but only computational hiding. Note that an unbounded adversary can simply try all possible $r\in Z_q$ till it matches $g^r$ and then with this knowledge try all possible $m\in Z_q$ till it matches $g^mh^r$.

Now, if you would only publish the second component in ElGamal, i.e., $g^mh^r$, as commitment and discard the first, this actually is a Pedersen commitment (as the setting you use is identical - i.e., working in a prime order $q$ subgroup of $Z_p^*$). The problem is, that when using this modified type of ElGamal encryption and the person computing the commitment knows the secret key $x$ with $h=g^x$, the ciphertext component $g^mh^r$ is no longer a binding commitment. Observe that you then can choose an arbitrary $m'\in Z_q$ and solve the equation

$m+xr\equiv m'+xr' \pmod q$

for the only unknown $r'\in Z_q$, which implies that

$g^mh^r = g^{m'}h^{r'} \mod p$

holds and thus, the commitment to $(m,r)$ can be opened to other arbitrary values $(m',r')$ (thus not binding at all).

Note that in fact it is essential for Pedersen commitment that the parameters $g$ and $h$ need to be computed by a trusted third party such that the discrete log $a$ between $g$ and $h$ is unknown. Otherwise you would have the same problem as with this "take the second ciphertext component of ElGamal encryption" as commitment. If you want to have such a property you obtain a trapdoor commitment with trapdoor $a$ (which allows you to arbitrarily open the commitment if you know the trapdoor $a$ as discussed above).

Edit:

As Ricky Demer mentioned in his comments I assumed that the commitment is non-interactive. If the receiver chooses the parameters for the commitment scheme and sends them to the sender, then unconditional hiding is given (it must only be ensured that the sender does not know the dlog between $g$ and $h$).

As tylo mentioned in the comments it is also interesting to look at the binding properties of both approaches.

Pedersen commitments are computational binding under the dlog assumptions as seen above.

The exponential ElGamal version - publishing $(g^r,g^mh^r)$ - is, however, unconditionally binding as the first component $g^r$ uniquely determines $r$. Thus, this means that also $m$ in $g^mh^r$ is uniquely determined.


How to provide secure password based encryption with password reset option

In every of these options the essential step is to save it in secure place. Instead of implementing any of these options, just tell the user to keep the password in the same secure place that you have in mind for the 2nd key. All major risks will be the same as for keeping there the 2nd key, but this solution will cost you nothing - no implementation, no costs.
To answer your question precisely: What is the pro ...? I don't see any "pro", because they are not more secure than keeping the original password at the same secure place. To "cons": additional complexity to implement such process and to maintain it without getting any more security.
In case of option 3 additional complexity (also without additional security) comes from the fact that 2 of 2 keys are needed. This is effectively the same as "simple" splitting of the key into 2 parts without using any complex method.


How can an amateur introduce a cryptographic algorithm?

First, if it's a secret-key cipher, then you'll never find any proof of security—at best you'll, exhaust the standard cryptanalysis techniques and exhaust the brilliant ideas of the brilliant cryptanalysts.  If it's a public-key cryptosystem, then at best you can prove reduction to a widely understood uniformly hard problem.  If you're not already familiar with these facts, you won't get the attention of serious cryptanalysts.

Second, you need to convincingly demonstrate (a) that you understand the standard cryptanalysis techniques, and (b) that it does not fall to them.  Cryptanalysts don't want to waste time doing your homework.  If you haven't already done your homework, you won't get the attention of serious cryptanalysts.

There's no good textbook of which I'm aware on this subject, but you might start with

  Bruce Schneier, ‘Self-Study Course in Block Cipher Cryptanalysis’, Cryptologia, 24(1), January 2000, pp. 18–34.
  https://www.schneier.com/academic/archives/2000/01/self-study_course_in.html

Third, if you want this to be anything more than an amusing intellectual exercise for bored cryptanalysts whose attention you've gotten, your cryptosystem has to fill a niche that nothing else does.  Is it faster or lower-energy on some significant platform than every other cipher providing comparable security?  Does it fill a specific need that no other cipher does, like a weird block size that is important for some particular reason?

For example, Gimli is a sponge with a much smaller state than Keccak-f1600, conveniently fitting in registers on more platforms, out of which one can build all manner of secret-key crypto gizmos.  (Gimli is a very new design, with some preliminary theoretical cryptanalysis.)

If you propose a general-purpose stream cipher that's not faster than software ChaCha or hardware AES-CTR, or a general-purpose collision-resistant hash function that's not faster than software BLAKE2b or hardware SHA-3, you won't get the attention of serious cryptanalysts who aren't either just bored or hoping their novel pet cryptanalysis techniques that failed to break the aforementioned ones might break something.

This applies even to designs that already have been published: Maybe RIPEMD160 resists collisions better than SHA-1 does, but it's not worth the time of most cryptanalysts to study it.  Maybe CAST6 is a better 128-bit block cipher than AES, but it's not worth the time of most cryptanalysts to study it.

Finally, if you want to get the attention of cryptanalysts, don't start with your cipher—start by showing that you are a competent cryptanlyst by using novel techniques to break crypto!  Best if you can break existing cryptosystems that were previously unbroken, or break them worse than the best published attacks.  This may be easier if you study cryptosystems that have received relatively little attention, including your own.

If you have a write-up demonstrating all of this—either a description of a novel cipher with evidence of resistance to standard cryptanalytic techniques and a reason to be interesting, or a novel cryptanalytic attack on an existing cipher—then a first step would be to submit it to the IACR cryptology eprint archive.  That won't impart the kind of serious review that, e.g., the AES and SHA-3 competitions did, of course, but it may catch the notice of some cryptologists and will be easier to show to someone whose review you are seeking, and if you do get the attention of a serious academic cryptologist they will likely have followup suggestions for publication venues.


For enciphering messages with AES in CTR mode, do I need a different key for each message?

To fully answer your question, let me go over the exact way in which CTR mode works.  Following the diagram below:

CTR mode takes in a 96 bit nonce and a 32 bit counter that is incremented with each block.  This 128 bit value is then put through, let's say AES encryption, with either a 128, 192 or 256 bit key.  This same key is used with every block.  A 128 bit output from the AES encryption is produced and this value is then XORed with the first 128 bit block of plaintext.

Now, we have produced the first block of ciphertext.  This same technique is done for each block of plaintext using the same key, but simply incrementing the counter each time.  Due to this design, padding is not necessary for the final block of plaintext and each block can be encrypted at the same time in a parallel fashion.  You should never repeat nonce/key pairs, as this will make it very easy for an adversary to gain knowledge of information.  CTR mode is basically a key stream that produces an overall key to be XORed almost like a One Time Pad.

You may repeat keys for different messages, as long as the nonce and counter are different.


Why can't we use the first block of AES-CBC as MAC

The MAC value should be calculated over all of the input, not just the first block. The chaining of CBC makes sure that the bits in the last block of ciphertext depends on all the previous blocks.


What are the rules for using AES-GCM correctly?

Rules or your obligations

Key generation: select a key uniform randomly, and keep it secret.

(Key,IV) Resue: An $(IV,Key)$ pair must never be used again.

Maximum file size: The recommended IV is 96 bits so 32 bit counter left. This means that the counter can count at most $2^{32}$. the first two are used so there is at most $2^{32}-2$ calls of CTR encryption. Therefore for an IV, one can encryption at most $2^{32} - 2$ blocks, or $2^{36} - 32$ bytes, or $2^{39} - 256$ bits. This is around $\approx 68$ gigabytes. You should stop way before, see more in advices section.

Check the authentication tag before decryption. If there is a mismatch, throw an error.

Tag size: use the recommended tag size 128-bit. You should not trim the tag size too much. For the full details of the tag security, see this nice posts;

Does GCM (or GHASH) only provide 64-bit security against forgeries?

GMAC vs HMAC in message forgery and bandwidth

Key size: Prefer 256 bit, though 128 bit AES is secure. In AES one will slow around %40 if uses 256 bit AES instead of 128-bit AES.

IV size: One can provide an IV longer than 96 bits, however, that will cause an additional GHASH call to convert into 96-bits.
$$\textbf{if } \operatorname{len}(IV) = 96 \textbf{ then } Y_0 = IV \mathbin\| 0^{31}1 \textbf{ else } Y_0 = \operatorname{GHASH}(H, \{\}, IV)$$
With larger One lost the counter/LFSR's deterministic IV generation. Stick to use 96 bits.

Advices

For IV generation, NIST suggests two types 800-38D

Deterministic Construction In a short manner use counter/LFSR to prevent IV reuse under the same key. One needs to store the last counter/stage to advance. During system failures, these values may not be recovered correctly, A combined mode half random, half counter/LFSR can eliminate this or start with a fresh key.
This counter should not be confused with the internal counter used in the CTR encryption.
The deterministic IV generation with an LFSR recommendation of the NIST is very effective in the case of a hardware implementation of the AES-GCM as pointed in this answer

RBG-based Construction RGB is a Random Bit Generator. In short from the NIST: The random field shall either consist of

an output string of r(i) bits from an approved RBG with a sufficient security strength, or
the result of applying the $r(i)$–bit incrementing function to the random field of the preceding IV for the given key

Random IV vs Sequential IV
AES-GCM best works 96 bit IV and when the IV is generated sequentially. If you choose random IV then due to the IV collisions under the same key, then the limit on the number of messages to encrypt under the same key is much smaller than sequential 96-bit IV.

Limit the message size gainst forgery: Put a limit to message size to eliminate the adversary's forgery advantage. It is linear in the maximum message size (not, e.g., the average): merely sending a single $2^{36}$-byte message makes the adversary's task four million times easier than if you limit all your messages to $2^{14}$

Limit the message size gainst DOS attack: Put a limit to message size to prevent Denial-of-Service by selecting the amount as the size of memory can an adversary reject before rejecting for forgery.

If you need to use AES-128; during the negotiation for the key agreement, it is better if the pair not only agrees on a key but also on a random initial counter. Then increment on it with a counter/LFSR.

Little deeper

(IV,key) reuse: This can lead to lost of confidentiality since the underlying encryption is performed by the CTR mode.
A CTR mode converts a block cipher into a stream cipher. Like all stream ciphers, if the keystream is reused crib-dragging technique can reveal the messages. Once the messages are removed the keystream is also revealed. However, this doesn't mean that AES is broken here. One still needs to execute a KPA attack and AES has known to be secure.
Reuse can also have catastrophic result of forgery.

Thanks to SqueamishOssifrage's comments and suggestions on the chat.


Pollard's Rho - Constructing the Random Function

If you generate group elements at random as you suggest then you can indeed invoke the "Birthday Paradox" to find logarithms in time $O(\sqrt p)$. Unfortunately your storage requirements are the same and for cryptographically interesting group orders your method is therefore far from optimal.

The fastest way for groups with (apparently) no exploitable structure (like elliptic curves) uses "distinguished points" as it allows you to tailor your parameters to suit the storage you have available. Then there are issues relating to whether you're just finding one discrete logarithm or many.

Having said that, I believe that pretty well any reasonable random number generator will be satisfactory for your method. If a particular method of generating random numbers had a performance consistently different from normal then that would probably be of independent mathematical interest, worthy of publication.


Given paramaters of an Edward's curve and x, determine a y value if it exists

The equation for an Edwards curve is $x^2 + y^2 = 1 + dx^2y^2$. Assuming you know the curve parameters then, given that you know $x$, you are solving the above equation for one unknown, namely $y$. We can rewrite this as a quadratic equation in one unknown and solve it. Note that all operations are $\bmod{p}$ where $p$ is the characteristic of the field the curve is defined over (remember that dividing by $z$ is equivalent to multiplying by $z^{-1}\bmod{p}$, square roots also have different rules).

$$x^2 + y^2 = 1 + dx^2y^2$$
$$y^2 - dx^2y^2 + x^2 - 1 = 0$$
$$(1 - dx^2)y^2 + (x^2 - 1) = 0$$

Now let $a = (1 - dx^2)$, $b = 0$, and $c = (x^2 - 1)$ (so we have $ay^2 + by + c = 0$ i.e. a quadratic equation). Note that you can also move some terms around in the upper equation and end up at the same result.

$$y = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$
$$y = \frac{-0 \pm \sqrt{0 - 4(1 - dx^2)(x^2 - 1)}}{2(1 - dx^2)}$$
$$y = \frac{\pm \sqrt{-4(1 - dx^2)(x^2 - 1)}}{2(1 - dx ^2)}$$
$$y = \pm \sqrt{\frac{1 - x^2}{1 - dx^2}}$$

Now substitute in $x$ and $d$. Note that there are two solutions to the equation. Without your x coordinate having some sort of encoding that indicates which y value should be used it is impossible to recover the "correct" y as both values result in distinct valid points.


A block cipher with independent keys for each round

John Kelsey, Bruce Schneier and David Wagner proposed paper "Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES" and they presented new attacks on key schedules of the block ciphers. About "A 768-bit DES variant uses independent round subkeys" they said:

  A 768-bit DES variant uses independent round subkeys [Ber83]. This
  variant will be much weaker in some situations: there is a very simple
  related-key attack needing just 15 related keys and 60 chosen
  plaintexts. Obtain the encryptions $E(k, p)$ and $E(k' , p)$, where k is
  obtained from k by flipping some bits in the last round subkey; this
  can be thought of as a differential $1R$ attack with a characteristic of
  probability 1. The last round subkey can be recovered with four chosen
  plaintexts, and then we can peel off the last round and repeat the
  attack on 15-round DES. This attack can also be optimized for the case
  when related key queries are very expensive to achieve a complexity of
  one related key and $2^{16}$ or so chosen plaintexts. For nearly any
  product block cipher, if it’s possible to flip bits in a cipher’s
  expanded key, it’s possible to mount an XOR differential attack on the
  last round of the cipher. This may be useful in attacking some systems
  that leave expanded keys vulnerable to change.

So if the algorithm is DES the answer is: NO.

Charles Bouillaguet, Patrick Derbez, Orr Dunkelman, Nathan Keller and Pierre-Alain Fouque proposed "Low Data Complexity Attacks on AES". They said:

We present several attacks on up to four rounds of AES requiring up to ten chosen plaintexts. Most of the attacks are based on the meet-in-the-middle approach. Some of the attacks exploit heavily the AES key schedule, while others apply even if the subkeys in AES are replaced by independent subkeys. The attacks are summarized in Table 1.

The attacks are applicable to up to 7-rounds of Rijndael. Since the minimal number of rounds in the Rijndael parameter settings proposed for AES is 10, these attacks does not endanger the security of the cipher.

By now there isn't any attacks against full-rounds of Rijndael key schedule or full-rounds of Rijndael with independent subkeys.

So if the algorithm is AES the answer is: By now YES
But the answer is depending on future researches. And in general the answer is depending on the algorithm.


RSA key length choice for TLS when confidentiality not important?

1.
To clarify: The critical time period here is one year (after wich the certs are changed). With the cracked RSA key the attacker can decrypt the traffic and do nan-in-the-middle attacks, posing as a valid hardware device.

Let us take the numbers determined by experts. In their paper on cracking the 768-bit RSA key the researchers state that they needed about $2^{67}$ instructions. When you look up current pricing for the Amazon EC2 cloud you get two Intel Xeon E5-2670 for 2.4\$ per hour. That is roughly $$2 CPUs \times 3\ GHz \times 8\ cores \times 8 FLOPS/cycle = 384\ GFLOPS$$ for 2.4\$/hour. That makes the cost of cracking a 768-bit RSA key about a quater million Dollars (on CPUs). Or 143 instances working for one month, or 1000 instances working for 4 days, etc. This is of course very simplified but gives you a rough idea.

Computing power doubles every 2 years and with special hardware, like GPU computing you can significantly lower the pricetag (modern cards operate in the order of TFLOPS see specs on AMD or NVIDIA websites).

A computer packed with 3 GeForce GTX 780 Ti (cost all together about 3000\$) can achieve 15 TFLOPS. This cracks a 768-bit key in 113 days, well under one year. So your key is definitly not safe from a moderatly determined attacker.

As for a 1024 bit key they state it would take 1000x more time or money. Very costly, but totaly out of reach in 5 years?

Other sources state a 2048 bit key would take $2^{32}$ times longer. So you are definitly save here.

But if I understand your scenario correctly you might be able to avoid the problem altogether: The computing cost of a larger RSA key only has to be paid once. During the inital handshake of the connection (generating the AES key). If you do not have a higly dynamic environment (meaning devices coming and going all the time) this cost will not matter much.

2.
For generating a few certificates a year you do not need a special module. This is only neccessary if you need massive amounts of randomness/entropy (e.g. if you need to produce a cert every second). Here is command to find out the (estimated) entropy of your system on Linux:

cat /proc/sys/kernel/random/entropy_avail

I would be more worried about the entropy available on those hardware devices (needed for the TLS handshake). If they are very simple microcontroles that might be a problem.

3.
Kind of answered that in question one.

Hope that helps!


Possible to determine equivalence of hash codes from different hashing functions?

Actually, if you define the $H_i$ functions properly, it can be done.

I'll make the simplifying assumption that we can treat the $H_i$ and $F$ functions as Oracles (that is, you're not allowed to look inside their implementation); I believe that it's still possible without that assumption (but the solution may be more complex).

For our primitives, we'll use FF1 with a secret key; and define:

$$H_i(x) = FF1_{key}( SHA256(x) || i )$$

This meets all the requirements of a secure hash function (e.g. it is collision resistant if we assume SHA256 is); in addition, the holder of $H_i$ cannot use it as a Oracle to compute $H_j$ for $i \ne j$ (as they don't know the $key$)

And, we can define a function $F$ that uses the secret key to decrypt both encrypted hashes, and compares the SHA256 values.  This will correct tell if the two original messages where the same (unless we happen apon a collision in SHA256)


A single password manager vs password generator/hash

Let's look at the risks.

Encrypted password database

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

Password generator (from a single master password)

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

* * *

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

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

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

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

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

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

* * *

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


What is the high level procedure to use ECDSA?

Is ECDSA the same as other digital signing that I calculate hash of
  message, encrypt the hash and append it to the original message?

No. From a user standpoint, you give the ECDSA module the message, it will hash it internally and then do some black magic with it (which includes drawing a random number) and output you a signature. If you want to test if your implementation is decent, ie does the hashing by itself, take a long message (like a couple of kB long) and give it to the function. If it "just works" then it is hashing, if not, well then it is not hashing.

  In ECDSA can I choose hashing function and some encrypting parameters?
  What I need to know about generating pair of keys? What else do I need
  to specify.

Theoretically you can choose the hashing function, practically things may get a little more difficult with SHA1 and SHA256 being the standard options for ECDSA (despite SHA1 being broken).

Key generation is straight-forward. You pick one of the named curves your library provides (preferably the number in its name should be larger than 240) and then call the function to generate the key. This function will then generate the public / private key pair for you, by drawing a random number and doing an operation known as "scalar multiplication". Do not try to generate a curve yourself, this is really hard to do. The "larger than 240" limitation should give you a curve with 120-bit or more security which is sufficient.


Potential weaknesses when combining hash functions?

For generic weakness no.
Consider two weak hash functions H(x) = 1
This isn't preimage resistant but obviously concatenating a 1 to a hash function does not make it easier to find a preimage to it.

And consider H(x)=x
A very different kind of weakness and concatenate the message or parts of it would be super helpful in finding a preimage for the other function.