Time taken for a brute force attack on a key size of 64-bits

Well, that's simple: $2^{64}/2^{30}$ is indeed correct. And since $2^{64}/2^{30} = 2^{64 - 30} = 2^{34}$ then that would be the answer. A simple recalculation would give you approximately 545 years. As you can see, 64 bits is pretty much on the border of being cracked by general computers. It is also about the same size as the SHAttered attack; these kind of attacks scale well, so just renting 640 cores for a year in a cloud service would probably do it.

Brute force basically scales linearly with the amount of keys. However, we're doubling the key size here, not the amount of keys. Growing the key size exponentially grows the amount of possible keys. It's a bigger step to go from 10 to 100 as it is to go from 1 to 10, both in decimals as in binary calculations.

545 years would however be the maximum time it would take to find a key by trying all of them. On average you'd need half of that time using a single core as the key may be either on the lower half or higher half of the key space (whichever way you split it in two equal size parts, as each key should be equally likely). Each additional bit in the key size doubles the key space. That means you could subtract a single bit from the key size to find out the average time it costs to brute force the key.

The calculation required to find out the time it takes to brute force a 128 bit key isn't that more complicated: $2^{2 \cdot 64}/2^{30} = 2^{128}/2^{30} = 2^{128 - 30} = 2^{98}$. The outcome of course is rather different though; you'd now need $10^{22}$ years. Or around 700 billion times the current life-time of the universe to try all the keys. Or 350 billion times the life of the universe if you average things out (yeah, right).

Then again, according to WolframAlpha $10^{22}$ years is only 3.3 times the half life of Calcium-76 so there may be some calcium atoms left to witness the end result. Again, you can drastically reduce the time by adding processors. However, you'd need too much processors and energy to bring it back to a value that is possible to crack in a life time. Better not try to brute force a properly randomized 128 bit key then.

Important: it may be that you're not trying to find the value of a single key, but you're trying to find the value of one of a million keys. This, of course, it much easier because the chance of finding one quickly increases. This, and the possible advance of quantum computing, may be enough reason to go for a 256 bit key strength.


What is different below two Ciphersuites?

The difference is that tls_aes_128_gcm_sha256 is TLS 1.3 and tls_ecdhe_rsa_with_aes_128_gcm_sha256 is used for the older TLS 1.2. The first cipher suite doesn't specify the key agreement algorithm and the authentication mechanism. Those are likely used, but they are specified / configured elsewhere in the TLS handshake.
TLS 1.3 is basically TLS-done-right; the two protocols aren't compatible, even if the last part of the cipher suite matches. It can however use the same key agreement and authentication mechanisms (and thus the same server certificate and key).

To quote OpenSSL:

SSL_CTX_set_ciphersuites() is used to configure the available TLSv1.3 cipher suites for ctx. This is a simple colon (":") separated list of TLSv1.3 cipher suite names in order of preference. Valid TLSv1.3 cipher suite names are:
TLS_AES_128_GCM_SHA256

OK, so we're talking TLS 1.3 here, let's look there:

Although TLS 1.3 uses the same cipher suite space as previous
versions of TLS, TLS 1.3 cipher suites are defined differently, only
specifying the symmetric ciphers, and cannot be used for TLS 1.2.
Similarly, cipher suites for TLS 1.2 and lower cannot be used with
TLS 1.3.

So we have two cipher suites that are largely identical to the message encryption / authentication used. However, one is for TLS 1.2 and also specifies the key agreement and the other is specific to TLS 1.3 and only specifies the message encryption / authentication.
For TLS 1.3 the reason why the other components are not specified is that they are negotiated during the handshake. This makes TLS 1.3 more flexible as it doesn't seem to specify all possible combinations in the cipher suite. However, you should remind yourself that the cipher suite is far from the only configuration parameter.
From TLS 1.3, section 4.1.1, Cryptographic Negotiation:

...
In TLS, the cryptographic negotiation proceeds by the client offering
the following four sets of options in its ClientHello:

A list of cipher suites which indicates the AEAD algorithm/HKDF
hash pairs which the client supports.

A "supported_groups" (Section 4.2.7) extension which indicates the
(EC)DHE groups which the client supports and a "key_share"
(Section 4.2.8) extension which contains (EC)DHE shares for some
or all of these groups.

A "signature_algorithms" (Section 4.2.3) extension which indicates
the signature algorithms which the client can accept.  A
"signature_algorithms_cert" extension (Section 4.2.3) may also be
added to indicate certificate-specific signature algorithms.

...

so basically the ECDHE option is now in supported_groups (DH is required for TLS 1.3) and RSA is in signature_algorithms, if present.

Short explanation of the components in the cipher suite:

tls : the protocol;
ecdhe : ephemeral-ephemeral elliptic curve diffie hellman for key agreement, which brings forward security;
rsa : signature algorithm when certificate authentication is used (for the server);
aes-128-gcm : block cipher & cipher mode to keep the messages confidential & authenticated;
sha256 : hash algorithm used for the PRF (used for key derivation).

Note that TLS 1.3 uses HKDF instead of a proprietary HMAC based mechanism in TLS 1.2 for the PRF. So although the TLS 1.2 and 1.3 cipher suites you mention may use the same primitives, the protocols differ somewhat (as explained in the initial section of this answer).


RSA: What would happen if you chose n to be a prime?

How would Bob decrypt her message?

That'd be easy, all we would need to assume that Bob has the public key.  If $n$ is a prime, he is able to compute $d = e^{-1} \bmod{\lambda(n)}$, because $\lambda(n) = n - 1$.  He can then raise the ciphertext to the $d$th power modulo $n$, and that's the padded plaintext.

Since anyone with the public key can do this, RSA based on a prime modulus is insecure.


One Step Decryption For Multiple Chained Encryptions

By definition, there exists such a function.  Your function $g(z)$ could be simply a table of all the possible values of $f(f(f(x, y), y), y)$ mapped back to one of the possible values of $x$.

I think that what you're asking is whether there is an efficient algorithm for unwinding this chaining.  Generally, with cryptographic algorithms, the answer is no, and this is intentional (see RichieFrame's comment about nonlinearity).

There are exceptions, though.  For example, with "raw" RSA, $f(x, y) = x^y \mod n$, for whatever $n$ is used alongside $y$ as the public key.  Then:

$f(f(f(x, y), y), y) = ((x^y)^y)^y \mod n = x^{y^3} \mod n$

Let $d$ be the private key (exponent) corresponding to $y$.  Then, you have:

$g(z) = z^{d^3} \mod n = x \mod n$.

In general, this property is something to avoid, because it often allows attackers to modify the contents of an encrypted message (to something useful) without being able to decrypt the message.  In the case of "raw" RSA, it leads to attacks; real RSA implementations use padding to make RSA not have this property.

Closely related: malleability


Collision likelihood from /dev/urandom for VMs using the same underlying hardware

There are at least two important things that can go wrong with VM randomness:

They could end up with the same "entropy" input and produce same/related numbers.
Someone with access to one VM could be able to predict the "random" inputs of another VM.

In a simple setup each VM has their own pool, they get initialized with saved values on startup and they make their own measurements that they feed into the pool. Only on first start (or two starts from a checkpoint), when they have constant initialization could they start off with identical numbers and be slow to gather enough entropy to diverge. (If you have a CPU with RDRAND/RDSEED this should never happen, since that is mixed into the pool frequently.)

The second issue is more difficult to gauge. Again, access to hardware random numbers avoids the issue, but theoretically the other VM could have influence on or be able to predict the "random" measurements otherwise.

It is common to use paravirtualization to handle the problem for good. By having the host generate independent random numbers for the guests, their random number generators will generate independent numbers.


After looking through some papers, I feel qualified to answer my question, for the record.
The scheme works and I've found no evidence that it has been broken. A good review is given in "A survey of ring signature" by L. Wang, which contains a section on linkable signatures.

The technique used in Liu's 2004 paper from the question makes O(n)-long signatures, where n is the number of public keys. There are more recent schemes commonly called "short LRS", which produce O(1) signatures. However, all schemes that I saw require some kind of trusted party to be involved in the generation of key pairs. This defeats the purpose of LRS I think, and anyway is unsuitable for my applications. From my superficial understanding, in O(1) schemes the danger of chosen key attack is somehow greater, and has to be compensated by including this key managing authority.

As for real applications, I found one (unfinished?) implementation of the 2004 scheme, and that's it.

So I've implemented the 2004 scheme and a similar, but more efficient scheme by the same authors. It's here: https://github.com/sorrge/LSAG . Public domain. Not reviewed by anyone yet, so no promises of its security.


How to represent point-at-infinity in affine coordinate

From a mathematical point of view this is not possible. I would say almost by definition because the point at infinity does not lie in the affine part. To be more precise:

Let $\mathbb P^2$ is the two dimensional projective space with coordinates $(x:y:z)$ and $\mathbb A^2 \subset \mathbb  P^2$ the affine part where $z \neq 0$ then one can see $X = x/z$ and $Y = y/z$ as coordinates on $\mathbb A^2$. Then $\mathbb P^2 \setminus \mathbb A^2$ is exactly the part where $z=0$ by definition.

Now if $E$ is the curve given by $y^2z = x^3 + axz^2 +bz^3$, then there is exactly one point of $E$ in $\mathbb P^2 \setminus \mathbb A^2$. Indeed by setting $z=0$ one obtains $0 = x^3$ hence $x=0$ showing that (x:y:z) = (0:1:0) is the only point of $E$ not in $\mathbb A^2$. This point (0:1:0) is the point at infinity and does not lie in $\mathbb A^2$ hence you cannot represent (0:1:0) in affine coordinates.


It actually depends on what you consider a hash function.

If we take a CRC (Cyclic Redundancy Check) as our hash function, then it is quite feasible; a CRC has a property that every output bit is a linear (affine if the initial state is nonzero, but the difference is unimportant) function of the input bits; hence we can generate a set of linear equations over the various bits of X in the expression $CRC( Message || X || MoreMessage ) = X$, and attempt to solve that (and find the solutions, if any).

I would further note that CRC does meet the criteria you gave; it can potentially have a large range (just make the CRC state large enough), and at first glance, if you just look at inputs and outputs, it does appear random.

Of course, a CRC is not a secure hash function; however you didn't specify a secure hash function.


Is security against semi honest adversary inheritable?

In general, no, you cannot do that. That is why frameworks like universal composability exist.

In the UC framework, you prove a protocol, $\pi_1$ is secure according to some adversary model. You do this by showing how $\pi_1$ is indistinguishable from some ideal functionality $\mathcal{F}_1$, where the ideal functionality is secure by definition (e.g., via the use of a trusted third party).

Then, say you are developing another protocol, $\pi_2$, that calls $\pi_1$ as a subroutine. You can replace the call to $\pi_1$ with a call to $\mathcal{F}_1$ in $\pi_2$. Prove the (UC-)security of $\pi_2$ run in this manner, which should be easier since you have taken a portion of it and replaced it with a "secure-by-definition" subroutine. The theorems behind the UC framework prove that if $\pi_2$ calling $\mathcal{F}_1$ is secure, then $\pi_2$ calling $\pi_1$ instead is also secure.

Without something like this, you cannot simply inherit security of protocols called as subroutines. The picture is different, however, if the protocols are run sequentially, as mentioned in the comment below.


What is the difference between PBE and symmetric key encryption?

As typically implemented, PBE takes a low-entropy, user-supplied password, adds some entropy to it, and thus strengthens it before turning it into a key. This key can then be used for symmetric encryption.

The problem is that the user's password often has so little entropy to start with. If an attacker learns the salt, digest method and quantity of iterations, he needs to keep trying to guess the pre-strengthened password, apply matching PBE-strengthening to his guess, and then use the resulting key to match up with ciphertext that was created with that key.

If the programmer used a decent digest method (such as PBKDF2 with HMAC SHA 256), a salt generated by a cryptographically secure pseudo-random number generator (CSPRNG) and a decent quantity of iterations (200,000 or more) then he can make it pretty expensive for attackers to guess the key.

However if the user's password is ridiculously easy to guess (such as "password") then even a good digest method and lots of iterations won't make much difference. You still need to force the user to choose sufficiently complex passwords, to maximize the entropy prior to any strengthening occurring.

OWASP has some best practices on enforcing password complexity.


Keeping the (initial) IV secret only adds security for the first block of your cipher text. The IV for the second block is by definition the first cipher text block, and so on. So if we would have the key but not the initial IV, we could decrypt the whole ciphertext except the first block. So it doesn't add much security, but it does add "management", as you do need to communicate the initial IV to any party you wish to be able to decrypt.

So normally the IV is just prepended to the cipher text and not kept a secret. This is no problem as long as the IV is random and non-predictable for every message or file we encrypt with that key. CBC in this mode has a standard security proof (for privacy only, of course, as we do not have integrity checking).

Another option is to have an implicit IV that depends on key material (that the recipient should know anyway to be able to decrypt), using hashes or other pseudorandom functions. This is done in some standards. This saves the 16 (if that is the block size) bytes expansion for explicitly prepending it. It adds some complexity, and expansion is not really an issue these days for things like file encryption. I would avoid it.


Can you help me with this DES variant analysis?

Each half of the key is 28 bits long, so there will be $2^{28}$ possible choices for each of them.

In the first part of your attack, you start with the known block of plaintext and encrypt it for the first 8 rounds using each possible left half of the key.  This gives you $2^{28}$ "half-encrypted" 64-bit blocks.  This is less than the birthday bound, so most likely the blocks will all be distinct, although there's a small chance (about 1 in $2^9$) of there being at least one collision.  Still, for practical purposes, we can assume the number of distinct half-encrypted blocks to be close to $2^{28}$.

In the second part of your attack, you start with the known block of ciphertext, decrypt it for 8 rounds using each possible right half of the key, and look the resulting "half-decrypted" block up in the list of half-encrypted blocks compiled in the first part of the attack.  Obviously, if the ciphertext is indeed the result of encrypting the corresponding plaintext with the modified DES algorithm you describe, there will be at least one match corresponding to the correct pair of half-keys.

As for the other half-keys, each of the $2^{28}$ right halves has a $2^{28}/2^{64} = 1/2^{36}$ chance of producing a half-decrypted block that, just by chance, matches one of the half-encrypted blocks computed in the first part.  Since these probabilities are essentially independent, the total expected number of "false positive" matches is $2^{28} \times 1/2^{36} = 1/2^8$.  By the law of rare events, the actual number of false positives is approximately Poisson-distributed, and, since the expected number is significantly less than one, the probability of there being at least one false positive is also approximately equal to the expected number.

Thus, with probability about $1 - 1/2^8$, just carrying out this meet-in-the-middle attack on one pair of known plaintext and ciphertext blocks will yield a single pair of half-keys corresponding to the correct key.  If you do get unlucky and end up with multiple candidate keys, testing them on a second plaintext / ciphertext block will rule out each of the false ones with probability $1 - 1/2^{64}$.

Edit: (Copied and extended from comments below.) All of the analysis above is in the ideal cipher model, i.e. it assumes that each of the halves of your modified DES can be treated as if it were a family of random permutations (of the set of 64-bit blocks) indexed by the corresponding 28-bit half-key. Of course, neither DES nor your modified version of it are actually ideal ciphers, but, like any good block cipher, they're designed to generally look like one, so for basic statistical analysis like this, the ideal cipher approximation is usually good.

If the statistical behavior of your (half-)DES variant turned out to be significantly different from an ideal cipher when the attack was actually carried out, this would most likely imply a much more fundamental weakness in the cipher than the mere(!) vulnerability to meet-in-the-middle attacks (not that it isn't a devastating vulnerability in itself, given the already low key length). In particular, note that several of the various known deviations of DES from an ideal cipher, such as the complementation property, don't really apply here since we've fixed the input.

As for the $1/2^9$ collision rate, $2^{28}$ keys give $2^{28}(2^{28}-1)/2 \approx (2^{28})^2/2 = 2^{55}$ pairs of outputs. Each of these outputs has approximately a $1/2^{64}$ chance of colliding (assuming independence, which is of course not really true, but a reasonable approximation), giving an expected number of $2^{55}/2^{64} = 1/2^9$ collisions. Since this is much less than 1, by the law of rare events it also approximately equals the probability of there being at least one collision.

Another way of calculating the collision probability is to note that, in order to get no collisions among the $2^{28}$ half-encrypted blocks, each of them must evaluate to a distinct 64-bit value as we calculate them one by one.  Thus, the exact probability of not getting a collision (under the ideal cipher assumption) is

$$\begin{aligned}
& (1 - 0/2^{64})\cdot(1 - 1/2^{64})\cdot(1 - 2/2^{64})\dotsb(1 - (2^{28}-1)/2^{64}) \\
\approx& 1 - 0/2^{64} - 1/2^{64} - 2/2^{64} - \dots - (2^{28}-1)/2^{64} \\
=& 1 - (0 + 1 + 2 + \dots + (2^{28}-1)) / 2^{64}  \\
=& 1 - (2^{28}(2^{28}-1) / 2) / 2^{64} \\
=& 1 - 1/2^9 + 1/2^{37} \\
\approx& 1 - 1/2^9
\end{aligned}$$


Proving the CCA-insecurity of El Gamal encryption scheme

No, as written, your technique doesn't work (as there's no specific reason why the encryption oracle use the same $y$ as the challenge ciphertext).

You need a different approach.  For one, the adversary doesn't need to depend on an encryption oracle; if he has the public key, then he can encrypt anything he wants.  What he does need to do is use the decryption oracle (as that performs an operation that the adversary cannot do himself).

So, how can the adversary create a ciphertext which is not the same as the challenge ciphertext, but when submitted to the decryption oracle, would tell him the answer?


AES: Why is it a good practice to use only the first 16 bytes of a hash for encryption?

Why is it a good practice to use only the first 16 bytes of a hash for encryption?

As you noted, it isn't.

But, the problem is not with the "16 bytes" part of the statement, or the concern for collisions. The problem is with the "hash" part.

16 bytes

As stated in one of the links you shared, AES only uses key sizes of 128, 192, and 256 bits (or 16, 24, and 32 bytes, respectively). So the key must be one of these sizes, because AES simply does not support other key sizes.

Trying to use a larger key could have a variety of possible outcomes depending on what the implementation chooses to do. It might raise an exception, or continue silently while only using the first N bits of the supplied key.

Hashing a password to use as an encryption key

Using a hash function such as MD5, SHA1, SHA2, SHA3, blake2, etc, would all be bad practice. The first two are obvious: MD5 and SHA1 are known to be weak in general.

But even using a strong cryptographic hash like SHA3 or blake2 would also be bad, because they were not designed to solve the problem of deriving a key from a password. Use of a cryptographic hash function is involved in this process, but it is not the entirety of it.

Good practice would be to use a dedicated key derivation function such as Argon2 that was designed to solve this problem. If your library doesn't support Argon2 but supports scrypt, bcrypt or PBKDF2, any of these three is also a reasonable choice.

Why/How

A normal hash function is designed to be fast and require little space.

A hash function designed for use on passwords is quite the opposite: it is a slow function that requires lots of memory access, in an attempt to try and optimize the function towards what a consumer CPU is good at, and minimize the potential for optimization with special hardware. Specialized hardware is usable by an attacker, but a legitimate user is limited to a commodity CPU; The goal is to try and use a function that cannot take advantage of special hardware to the extent possible.

Details about the hows and whys of password hashing are listed in this paper and quoted below (with minor modifications, e.g. removing citations and modified formatting):

  Cryptographic  Security: The  scheme  should be  cryptographically secure and  as  such possess the  following  properties:

  1) Preimage  resistance
  2) Second preimage resistance
  3) collision resistance.

  In addition it should avoid other cryptographic weaknesses such as those present in (some)Merkle-Damgård constructions(e.g. length extension attacks, partial message collisions, etc)

  Defense against lookup table /TMTOAttacks:

  The  scheme  should aim to make TMTO attacks that allow for precomputed lookup table generation, such as Rainbow Tables, infeasible

  Defense  against CPU-optimized 'crackers':

  The  scheme  should  be ‘CPU-hard’, that is, it should require significant amounts of CPU processing in a  manner that cannot be optimized away through either software or hardware. As such, cracking-optimized  (multi-core)  CPU  software  implementations (eg. written in assembly, testing  multiple input  sets  in parallel) should offer  only  minimal  speed-up  improvements  compared  to  those  intended  for validation (“slower for attackers, faster for defenders”).

  Defense against hardware-optimized 'crackers':

  The scheme  should be 'memory-hard', that is, it should significant amounts  of  RAM  capacity  in  a manner  that  cannot  be  optimized  away  through  eg. TMTO attacks. As such cracking-optimized ASIC, FPGA and GPU implementations should offer only minimal speed up improvements (eg. in terms of time-area product) compared  to  those  intended  for  validation. As  noted  by  Aumasson one of  the  main  scheme  design  challenges  is  ensuring  minimized  efficiency  on GPUs,  FPGAs  and  ASICs  (in  order  to  minimize  benefits  of  cracking-optimized  implementations)  and  maximized  efficiency  on  general-purpose CPUs (in order to maintain regular use efficiency).

  Defense  against  side-channel  attacks:

  Depending  on  the  use-case  (eg. for key derivation or authentication to a device seeking to protect against modification  by  the  device owner)  side-channel  attacks  might  be  a  relevant  avenue  of  attack.  Password  hashing  schemes  should  aim  to  offer  side-channel resilience. With regards to password hashing  scheme  security  we  will  focus on  security  versus  the cache-timing type  of  side-channel  attacks  given the existence of such attacks against the commonly used scrypt scheme. The  second category of side-channel  attacks  we  will take  into consideration are so-called Garbage Collector Attacks (GCAs). GCAs have been discussed in  literature as an instance of a 'memory leak' attack relevant to password hashing scheme security. GCAs consist of a scenario where an attacker has access to a target machine's internal memory either after termination of the hashing scheme or at some point where the password itself is still present in memory (the so-called WeakGCA variant)...


In finite field elliptical curve, is the addition of any two points on the curve guaranteed to land on the curve?

Adding two points on a curve following the addition law will always give another point on the curve.  That's part of what it means for the curve to form a group.

The addition law is defined relative to a particular curve and a particular field.  For example, consider the field $\mathbb F_3$, i.e. the integers $\{0, 1, 2\}$ with arithmetic—addition and multiplication—performed modulo 3, and consider the curve $$E/\mathbb F_3 : x^2 + y^2 = 1 + 2 x^2 y^2.$$  The point $(1, 0)$ (i.e., $x = 1, y = 0$) is on this curve, which you can check by a simple calculation.  The point $(2, 0)$, however, is not.  (Exercise: List, for every possible $x, y \in \mathbb F_3$, whether $(x, y)$ is on the curve.  There are only nine of them!)  The addition law $$(x_0, y_0) + (x_1, y_1) = \left(\frac{x_0 y_1 + x_1 y_0}{1 + d x_0 x_1 y_0 y_1}, \frac{y_0 y_1 - x_0 x_1}{1 - d x_0 x_1 y_0 y_1}\right)$$ always gives another point on the curve.  For example, $(2, 1)$ is also on the curve, and $$(1, 0) + (2, 1) = \left(\frac{1 + 0}{1 + 0}, \frac{0 - 2}{1 - 0}\right) = \left(1, \frac{-2}{1}\right) = (1, 1),$$ which you can check by another simple calculation.

That addition law always works for the points $(x, y)$ on $E$ for $x, y \in \mathbb F_3$, but does not always work for every curve or every field.  For example, it does not work for $$E/\mathbb F_7 : x^2 + y^2 = 1 + 4 x^2 y^2$$ because $4 = 2\cdot 2$ is a quadratic residue in $\mathbb F_7$.  (Try it with $(1, 5)$ and $(4, 5)$—you'll get a denominator which is a multiple of 7, which is equivalent to zero in $\mathbb F_7$, which you can't divide by.)  Not every curve can even be written in this form, which is called Edwards form; for example, curves of prime order, such as NIST P-256, have no Edwards form.  Other forms of curves have different addition laws, which work on different subsets of points and in different cases.


This method isn't deterministic. That is, just because a keyword has the lowest chi-square value, that doesn't mean it's the keyword. All it means that there is a good chance that it is the keyword. It's not a guarantee. You should look at the first several likely options to see if the keyword lies there. If you want to automate this, you could compare the possible keywords against known words using some dictionary file.


How do you communicate the hash function used with RSA signing?

Normally, yes, the hash algorithm in use is communicated beforehand.  For example, sending an algorithm identifier during the TLS/SSL handshake process.  However, depending upon the "padding scheme" in use with RSA, it may be possible to determine which hash algorithm was used from the signatures themselves.

Some padding schemes encode information specifying the hash algorithm that was used to generate the hash into the padding data.  "PKCS #1" is possibly the most well-known padding schemes that does this.

When data is signed in this manner, you can determine the hash algorithm used to generate the hash by decrypting the signature--taking it to the power e--then examining the data.  This check must be done carefully, because otherwise you might cause security breaks (Nintendo Wii comes to mind).

In PKCS #1, you take a hexadecimal representation of the hash, shown here in big-endian form, and prepend padding to the front.  The format of PKCS #1's padding is like this:

00 01 FF FF FF ... FF FF 00 <der> <hash>

(FF's are added until the entire byte string is the length of the RSA modulus.)

The <der> is an ASN.1-encoded identifier of the hash algorithm unique to that algorithm.  For example, the following identifier represents SHA-256:

30 31 30 0D 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20

Thus, the following would be a 768-bit big-endian signature block of an empty string, using SHA-256:

00 01 FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF 00 30 31 30
0D 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20
E3 B0 C4 42 98 FC 1C 14 9A FB F4 C8 99 6F B9 24
27 AE 41 E4 64 9B 93 4C A4 95 99 1B 78 52 B8 55

If you saw this string, you could determine the hash algorithm by checking for the 00 01, followed by a string of FF bytes, then a 00 byte.  Following it should be a known hash algorithm's DER, then the number of bytes present in that algorithm's digest, then the end of the block.  If all of these exactly match, it is a possible signature, so you could then use that hash algorithm to verify that the data matches.

Just make sure that you only allow hash algorithms that you approve of.


how long does the cycle length have to be in stream ciphers?

There's a bioinfomatics paper that might be of interest.  Good Practice in (Pseudo) Random Number Generation for Bioinformatics Applications suggests some values to the maximum run length of a PRNG.  Not strictly crypto, but I've not seen anything else.

In summary, it says that Knuth recommends a max. output of states /1000. However there is also a much more conservative limit of (states)^(1/3).

I'm not sure of how you exactly determined your baby Spritz cycles, but for comparison consider the grown up version with the full 256 byte permutation and assume that all states are achieved.  (This may not be possible due to the creation of weak states.) The conservative estimate would suggest that you could output ~10^167 bits of key material.

For N = 6, I estimate that you couldn't get a single safe bit from it if you follow the guidance above.


Could a 6502 CPU safely compute a SHA-1 hash in a reasonable length of time?

Yes, a 6502 can compute SHA-1 in a reasonable time: less than $\lceil(k+9)/64\rceil/5$ second for a $k$-byte message on a 1 MHz 6502 as on the 1977 Apple ][. E.g. 0.2s for up to 55 bytes. We need like 128 bytes of RAM excluding the hashed message. Code likely fits 1 kbyte of code including constants.

Note: I do not know clock speed, RAM and code size resources on a Tamagoshi.

I'm basing this on a commercial implementation I wrote for the 8031/8051, another 8-bit CPU (from an old post). My 660-byte code (including tables and C interface) is well below 50,000 CPU cycles per 64-byte block (where many instructions on registers are 1 cycle, and external memory access is 2 cycles; one cycle lasts 12 external clock periods of the original 8051, common variants reduce that to 6 or less). That code is not optimized quite to the max for speed, because the customer was short on easily addressable internal RAM, and code size was a consideration too. On the 6502, I estimate the number of CPU cycles would be less than 4 times that with unrolled code using zero-page addressing, that is less than 200,000 cycles. I would not be surprised if things could be brought down to 120,000 cycles or so. I second Poncho's comment that 83,700 cycles seems rather optimistic.

The most natural code is constant-time, thus at least a side-channel by timing is easy to avoid. Probing, and power/electromagnetic emission analysis are credible security threats, if an adversary can approach the hardware.

Note: I know no security CPU that used the 6502, but many have used the 6805 or derivatives, which are very comparable 8-bit CPUs. Some are still in active use.


Choosing between simple Hash and HKDF to derive the second key used for MAC

The HKDF paper answers this question at length.  Section 8 in particular seems to be the most relevant.

But perhaps you may find that the explanations are very technical.  To help you out a little bit, the general flavor is this: the security of nearly all modern cryptographic algorithms is conjectural—we don't have unconditional proof that they are actually secure, but rather arguments in forms like this:

Heuristic: "A lot of really good cryptanalysts tried to break the algorithm, but haven't succeeded."
Conditional proof: "If you can break this algorithm, then you can break this simpler building block that we believe is secure."

The difference between your proposed uses of SHA-256 and HKDF comes down to HKDF being more careful and pessimistic.  We don't have proof that HKDF is more secure than SHA-256 in your application, but the arguments for HKDF's security are better than those for SHA-256 because they rely on fewer and/or weaker untested premises than your use of plain SHA-256 would.

But it's also entirely possible that simple SHA-256 would be secure in this application.  Do you want to bet on it?  (Lots of systems do, so far successfully.)

So applying this to your comment here:

  But I am not stringent about these details, and if simple hash has no serious flaw I will use it because it seems much simpler.

...the thing to remark is that you're looking at the issue backwards—you're proposing to use the simple hash unless somebody can prove to you that it's insecure (which it might not be!).  But the way cryptographers look at it is that you shouldn't use the hash function unless you can articulate some good (even if inconclusive) reason why it's secure (e.g., by conjecturing that SHA-256 behaves similarly to a random oracle).


Standard tools for deterministic RSA key generation using seed?

For generating RSA keypairs from BIP39 mnemonics, a quick search give me three tools. but it is a bad method for deriving key pairs. A better method is using Key Derivation Functions with a standard tool like GnuPG.


You're missing the most important strength of HMAC: it comes with a proof of security (under some plausible assumptions).  The outer key plays an important role in the proofs.  The best place to learn more is to read the HMAC papers:

Message authentication using hash functions: The HMAC construction, Mihir Bellare, Ran Canetti, Hugo Kawczyk, CryptoBytes Spring 1996.
Keying hash functions for message authentication, Mihir Bellare, Ran Canetti, Hugo Kawczyk, CRYPTO '96.

In particular, it is very important for their proof that the outer function be keyed.  In your scheme, the outer function is not keyed, so their proof of security will not apply.

As they explain in the paper, the role of the inner function is to provide collision-resistance (to compress a long message down to a short fingerprint, in a way so that someone who does not know the key cannot find a pair of messages with the same fingerprint), and the role of the outer function is to act as a message authentication code on this fingerprint.  Their security proofs show that if the inner and outer functions each correctly implement their roles, then the combination (HMAC) will be a secure message authentication code.  Because the outer function needs to be a secure message authentication code, that means the outer function needs to be keyed for their proof methodology to apply.

Read the papers.  They are surprisingly readable, for a theoretical piece of work.


No, it doesn't help.  It doesn't hurt either; as long as you don't repeat keys, the probability of success is always the same.  That is, if there are $2^n$ possible keys, and you test $\lambda$ of them, the probability you hit the right one is always $\lambda / 2^{n}$.

A key generated by a high quality random number generator (or a good key derivation function) is equidistributed; every possible value has an equal probability of being the correct one.  Yes, most keys will have approximately the same number of 0's and 1's; but that's because most possible values will have approximately the same number of 0's and 1's.


If I read it correctly , just use the ASCII table, e.g. as given here. So "Please" is just the sequence of bytes (hexadecimal) 0x50  0x6c  0x65  0x61  0x73  0x65. Concatenation of those values gives a word (still hexadecimal, but we could have used bits as well, it's just more typing) 506c65617365 which is the decimal number $88426487575397$ (using a hex to decimal conversion tool, or bc in my case). This is the number which is raised to the power $d$ to create the signature of "Please".

As an idea to use $(xy)^k \bmod{N}  =x^k y^k \bmod{N}$ for all $x,y,k$, and of course $(x^d)^e = (x^e)^d = x  \bmod{N}$ for all $x$. This allows for manipulation in a multiplicative way for given signatures (or encrypted values).


Has any crypto hash function been proven to be surjective?

The answer is YES for constructions of hash functions that are not used in practice. For example, there is a construction by Damgård that is based on the discrete log problem and works by computing $h(x_1\|x_2)=g^{x_1}\cdot h^{x_2}$, where $g$ is a generator of the group. If $h$ is chosen randomly in the group, then it is hard to find a collision in this function, unless you can solve the discrete log problem. By applying the Merkle-Damgård transform, you get a hash function that takes inputs of any length. Thus, this is a collision resistant hash function.

It is easy to see that this function is surjective. Specifically, $g$ is a generator of the group, so for every $h'\in\mathbb{G}$ and for every $x_2$ there exists a value $x_1$ such that $g^{x_1}\cdot h^{x_2} = h'$.


Why doesn't Wang's attack work on SHA-1?

The message expansion step in SHA-1. The compression functions for MD4,MD5, RIPEMD and I think HAVAL only re-arrange and re-use words in the message block.

SHA-1 will expand the message from 16 words to 80 words using a rotation and XOR operation. The additional 64 words are a function of every word of the message block.

Because of this additional dependence on previous words in the block, Wang's attack will not work.


What you are looking for is a permutation,  and not normally what we call a hash function.
The identity function is a permutation and so is modular addition. And many more.

You probably want some other properties of cryptographicly secure hash functions such as preimage resistance.

A pseudo random permutation will suffice any secure block cipher such as AES will meet the bill.

Note this in itself isn't a usefull hash function, for hash functions we want a compression function where the output is smaller than the input. From pigeon hole principal it is obvious that if the output domain of a function is smaller than it's input domain it must have collisions and can not be a permutation.

With cryptographically secure hash functions like SHA-3 we fully expect there to be many collisions even when the input domain is restricted to match the output domain we simply don't know how to find any such collisions which is a basic requirement for cryptographically secure hash functions.


SHA-1 requires utf-8 and reordering of bytes

Text is supposed to be utf-8 encoded / one character should be 8 bit long. this makes sense, since the same text should always return the same hash, but I couldn't find anything about it in the RFC. Is there any place where this is documented?

This isn't a requirement of SHA-1, but rather appears to be some requirement of the context in which you encountered this implementation.

SHA-1 doesn't assume anything about the bytes in the message; they may be text in any encoding, image data, random bytes, whatever.  However, an actual user of SHA-1 who is hashing text would care about this.  Suppose two applications have the same text string, but one uses UTF-8 internally and the other uses UTF-16.  If each one just hashes its own raw memory bytes they're going to get different results even though their strings, textually, are the same.

  For some reason the bytes for each 32-bit word need to be reversed so the first byte comes last. e.g if we have chunk of 32-bit (reading from left to right).

This is an endianness conversion, so you should familiarize yourself with that concept.  This is in fact a requirement of SHA-1.  FIPS 180-4 says (p. 7):

    Throughout this specification, the “big-endian” convention is used when expressing both 32- and 64-bit words, so that within each word, the most significant bit is stored in the left-most bit position.

The RFC that you link says it this way (which is more confusing, I think):

    The least significant four bits of the integer are represented by the right-most hex digit of the word representation.  Example: the integer 291 = 2^8+2^5+2^1+2^0 = 256+32+2+1 is represented by the hex word, 00000123.

Whether you need to perform the step that you describe is context-dependent.  For example some CPUs are natively big-endian and wouldn't need that step—the bytes would already be in the correct order for the 32-bit operations that SHA-1 performs.  Others are natively little-endian and would need the conversion.  It can also depend on the details of some network protocol or library that you're working with.


How do substution-permutation networks work?

1) and 2) Either S0, or S1 is used for each 4-bit long part of block depending on key bits. 16 S-boxes are used in each round (because you split 64-bit-long block into 16 parts of length 4) of the Lucifer cipher, so each round needs a 2 byte long subkey.

Example:

16 starting bits of the key (the first subkey):

0 0 1 0 1 1 1 1 0 0 1 0 1 0 0 1 (2 bytes together)

S-boxes used in the first round:

S0 S0 S1 S0 S1 S1 S1 S1 S0 S0 S1 S0 S1 S0 S0 S1 (4 bit input/output each, 64 bits together)

3) No, not necessarily. Feistel's scheme is a general solution based on any S-box and any permutation P. The Lucifer SP is just one example of a possible SP. Feistel's scheme can be used with non-invertible function F, too. You don't need to use SP, although it is the most common choice.

4) and 5) Because this is how Feistel designed his scheme... He wanted to develop a hard-wired device he could safely use for both encryption and decryption and which would have all the great features provided by SP network (avalanche effect, non-linearity,...). You cannot use the same device for both encryption and decryption with basic SP network decribed on page 3 of your slides.

Why did he decide to rotate L and R after each round? If there is no rotation, R stays untouched - not very good for an encryption scheme, right?

6) Your slides are a little bit confusing, I think this picture illustrates Feistel's scheme better:

As you can see, if you place all XORs on the left and uses the right part always as an input of F, you rotate L and R after each round except the final one. Why not? Because the final rotation does not depend on key, so it would provide no extra security.

7) Because it is fast to compute XOR by our hardware and because the result depends equally on both input bits. If you used AND and the result was 1, you would know the input was 1 independently on the key, which is not what you really want, right? The same problem with OR and 0 result.

Linear cryptanalysis (based on comments):

Let's have a block cipher, output of which can be represented as a system of linear equations:

C1 = a11P1 XOR a12P2 XOR ... XOR a1nPn XOR b11K1 XOR ... XOR b1kKk

C2 = a21P1 XOR a22P2 XOR ... XOR a2nPn XOR b21K1 XOR ... XOR b2kKk

...

Cn = an1P1 XOR an2P2 XOR ... XOR annPn XOR bn1K1 XOR ... XOR bnkKk

where Ci stands for the i-th bit of the ciphertext, Pj is the j-th bit of plaintext, Kp is the p-th bit of the secret key and coefficients aij and bij are some wellknown 0/1 constants defined by the design of the cipher.

If you had enough plaintext-ciphertext pairs known for the same key, you could solve the equation system and find the key value. That would be a problem, right? That is why modern ciphers are never linear - you cannot write their output as a system of linear equations of input bits and key bits as above.

S-boxes in SP networks are always chosen not to be linear and even more, it must be difficult to approximate them by linear equations, otherwise the whole SP network would be vulnerable to linear cryptanalysis.

If you chose S-boxes of your SP network wisely, the whole network will be non-linear (therefore safe against linear cryptanalysis) and so will be Feistel's scheme based on this SP network.

However, this is just a basic intro. The linear cryptanalysis is very interesting and very complex topic and you should find some more detailed source of information in case you are interested.

Feel free to ask.


Secret key model for a compression function cryptanalysis?

Yes, if $K$ can be recovered from $H'=F(K,M)$, this is a weakness.  The function $F$ is not preimage-resistant, and an attacker may easily generate correct tags for new messages (this is called a forgery). The proposed MAC scheme, however, is terribly weak, and forged tags for other messages can be easily produced (length-extension property):
$$
T(M\mathbin\|M_p\mathbin\|M') = F(T(M\mathbin\|M_p),M').
$$
Still, if original $K$ can be recovered, forged tags can be produced for even shorter messages.

However, there could be many $K$'s that produce the same $H'$. If the cost of finding the original $K$ is still higher than the exhaustive search, then such attack is useless for forgery, as the attacker would have to use the length-extension attack. However, the compression function is still vulnerable to preimage attacks, which may be exploited in other constructions (for example, meet-in-the-middle attacks on hash functions).


Is there any definition for "generic attack" in context of cryptography or more specific "hash functions"?

A "generic attack" against a cryptographical primitive is one that can be run independently of the details of how that cryptographical primitive is implemented.  The most obvious case is a cipher that takes an $N$ bit key; the generic attack of brute force takes a ciphertext, and attempts to decrypt it with all $2^N$ keys; when we find the known (or plausible) plaintext, we are likely to have found the correct key.  This can be done no matter how the cipher uses the key.

When it comes to hash functions, there are three security assumptions we can make (preimage resistance, second preimage resistance and collision resistance), each with a corresponding generic attack.

When it comes to collision resistance (no one can find two distinct messages that hash to the same value), the generic attack is to hash a huge number of distinct messages until the same hash pops up twice.  This is called the "birthday attack" because, because of the birthday paradox, we expect such a pair after hashing about $\sqrt{2^n} = 2^{n/2}$ messages (where $n$ is the size of the hash).


How to calculate the branch number of a linear mapping?

As explained in the answer to the question here
the branch number of a linear mapping
$$
A:F_q^n \rightarrow F_q^n, \quad x\mapsto A\cdot x
$$
is the minimum weight of the linear code generated by the matrix
$$
G=[~I~|~A].
$$
For an arbitrary matrix $A$ this problem is NP hard, i.e., very hard. For structured matrices like the MDS matrix in AES the answer is known, see the link.
For the hardness result see Vardy's paper "the intractability of computing the minimum distance of a code". It or a related version is also available on citeseer. Since this code is linear minimum distance equals minimum weight.
https://ieeexplore.ieee.org/document/641542


What are the required properties of a PRNG to make it suitable for a stream cipher?

The best known algorithm to guess the next bit with probability near 1, without knowing the $n$-bit seed, has to cost approximately $2^\lambda$ bit operations, where $\lambda \leq n$ is the security parameter.

You can't determine this by feeding the output of the PRNG to a generic statistical hypothesis test, because by its very nature that statistical hypothesis test has only very limited hypotheses about how the PRNG might differ from a uniform random string of bits.  These generic statistical hypothesis tests are designed without particular knowledge of the PRNG.

You can really determine this only by feeding it to a swarm of cryptographers, but that works only if it appears as tasty to cryptographers as a bleeding hand to a piranha.

Cryptographers are a picky bunch that aren't much interested in spending their time on designs that aren't really interesting for some reason, like protecting trillions of euros of financial transactions, or performing better than modern standard stream ciphers today (like ChaCha, or AES-CTR with hardware acceleration) at the same conjectured security level.

And they don't usually want to spend time on designs whose designers haven't already studied and demonstrated to resist a litany of standard attack strategies.


Hash collision resistance of $\mathcal H^\prime(m) = \mathcal H(\mathcal H(m)|m)$

Your scheme is twice as slow as the original hash function.  If you were going to accept such a huge performance penalty, you'd be better off just picking a new hash function that (you trust) isn't broken.

Also, it's not clear to me how much security your construction actually adds.  I don't immediately see a proof that it is secure even if the compression function has some problems.  I'm not even sure how one would formalize this.  We'd have to assume something about the compression function, as you can't get something from nothing; but it's not clear what minimal assumptions about the compression function are sufficient to ensure that your construction is secure.


In many cases, 0x00 is treated as end of string. That is where the problem comes into play. So if I passed password\x00defgreallylongpassword into bcrypt, the password would be terminated after password due to the null byte. That is a very insecure password and can easily be found with a dictionary attack.

No one types null bytes into a password field, however. Where the blog post says this can occur in practice is if you first hash the password, then run it through bcrypt. There is a chance that the hash digest will have a null byte in it, which will cause the bcrypt code to truncate it.

The poster gets around this by suggesting that you base64 encode the hash of the password before feeding that to bcrypt. The base64 encoding will not have null bytes.

This hash then bcrypt construction has been proposed as a way around the 72 character limit of bcrypt. That said, I agree with this answer on our sister site. If you are using bcrypt for values that you expect might be larger than 72 characters, you are probably not using bcrypt for its intended purposes and should rethink what you are doing.


DTLS vs direct use of AES. What are the threats unique for direct use of AES instead of DTLS?

You appear to be quite familiar with the issues you face already, but I'm going to answer your question as literally stated nevertheless.

AES is a block cipher, so it needs to be used in a mode-of-operation in order to provide proper privacy (IND-CPA).

AES is a block cipher, so it needs to be used in a mode-of-operation in order to provide proper integrity (IND-CTXT).

Even with a good mode-of-operation (like AES-CCM), you don't get protection from replaying, reordering, and dropping of messages. For this you need a stateful mode-of-operation. What should this state be? It could simply be a number, but it doesn't necessarily have to be. In any case, this state needs to be managed and synchronized correctly between the two communicating parties. Can be tricky.
But in addition to this, you also need a choice of policy: do you allow messages to be dropped, but not reordered? Do you allow messages to be reordered, but not replayed? Do you allow some messages to be replayed/reordered within some window of acceptance? ...and so on, for any complicated combination of the above. Suffice it to say, getting this right can be subtle.

DTLS gives you all of the above. The question is, can you do it better? In theory it is certainly possible. But in the end you would probably end up with something which is very close to DTLS anyway. However, now you would have to implement all of this by yourself, giving you all of the problems associated with implementing cryptography that you are probably well aware of.
Ultimately, if DTLS gives you all of this out-of-the box, then trying to come up with something that replaces it strikes me as having a high risk of introducing problems and for relatively little reward. Thus, why not simply use DTLS? Or even better, use something built on top of (D)TLS which is explicitly designed for the IoT domain (like E4)?


Are there any additively homomorphic encryption schemes over $\Bbb Z_2$ besides Goldwasser-Micali?

Any additively homomorphic encryption scheme (with a large enough message space), e.g. Paillier. To do so, let the message space of the homomorphic encryption scheme be $\mathcal{M}$, you encode your message space $Z_2$ as follows:

choose an even number from $\mathcal{M}$ to represent 0, and an odd number to represent 1. One obvious choice would be simply 0 and 1. Let's call the two $m_0$ $m_1$ respectively

To encrypt, you encrypt $m_0$ or $m_1$ (all other messages are not allowed) using the homomorphic encryption scheme as usual.

To do homomorphic operations, you do the homomorphic operations as usual.

To decrypt, you decrypt as usual, then take mod 2 on the result to get your final result.

Here the parity of the values encodes messages in $Z_2$: even corresponding to 0, and odd corresponding to 1. We know

odd+odd $\rightarrow$ even (1+1=0 mod 2)
odd+even $\rightarrow$ odd (1+0=1 mod 2)
even+even $\rightarrow$ even (0+0=0 mod 2)
even+odd $\rightarrow$ odd (0+1=1 mod 2)

Thus it is correct.

The message space needs to be large enough so you can do enough number of addition operations without overflow (0 and 1 is actually the best choice to maximize the number of operations you can do).


What happens if the plaintext $m1$ from the first block of CBC is known to adversary?

For any modern cipher (including a block in CBC mode) with proper implementation, nothing harmfull happens when any part of the plaintext gets known to the adversary. This adversary's knowledge does not extend to other bits of the plaintext.

Argument: any algorithm that could extract some additional knowledge could be turned into one breaking CPA security. For CBC, CPA security can be proven from security of the block cipher, under the assumptions that the IV is random, the number of blocks enciphered remains low enough (like, less than $2^{b/2-n}$ where $b$ is the block size in bits and $n$ is a security parameter), and the decryption side does not leak information about the deciphered plaintext (such as, incorrect padding).


What quality of randomness is needed for randomized side channel countermeasures?

What quality of randomness is needed to secure a proper randomized cryptographic implementation?

It is essential that the random source used is unpredictable, including under attack. If it could be predicted, or made predictable (e.g. by pouring some liquefied gaz literally freezing the random source) the countermeasure could be neutralized or even become counterproductive.
It is important that the values produced are at least about uniform and independent. A marked bias could enable an attack. How uniform and independent depends on circumstances and attacker's skill.
It is important that the source is fast, because customers hate to wait, and a lot of randomness is typically used.

How is that randomness generated (usually)?

In modern security devices, by a physical True Random Number Generator complemented by some level of monitoring and/or post-conditioning. For a typical general description of what that hardware does, see e.g. items 151 and 152 in this public Target Of Evaluation. Details are usually secret, because knowing them could help attacks. More generally, resistance to side channels is a hide and seek game, and competitive practitioners of such game don't reveals their hides.  I am told that in Common Criteria evaluation schemes, there are points for how tightly the code is kept secret.


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

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


Homomorphic Encryption: how does the equality test on ciphertexts work?

No, what you want to do is not possible, because encryption is randomized: if you were to encrypt the same message many times, you'd get many different ciphertexts.  Therefore, Alice can't just compare two ciphertexts to see if they are the same; the two ciphertexts will be different even if they decrypt to the same thing.


How can i predict the next number of a long sequence of seemingly random numbers?

This sounds like a lot of work.

I would break this down into parts.  First, I would try to identify the random number generator being used.  From that, my goal would be to determine the starting seed, which would let me accurately predict future results based on past results.

I'd start with the NIST Random Number Generation statistical tests    In them, they offer 15 statistical tests for a random number generator.  I'd run the sample data through this battery of tests to see if it's actually random or not.  Important: if the tests reveal it is random, that could be evidence that a cryptographically secure random number generator was used to produce them.  I would stop searching as I would consider the problem unsolvable at that point.

I'd then test each of the random number generators that the original source might have used, such as rand(), and see if they reveal a pattern similar to that output of the mystery algorithm.

Once a potential random number generator is identified, I'd turn to published papers to see what kinds of analysis and reversals are known for it.


Is this method for exchanging private key using RSA sound?

You are inventing your own protocol.  Don't do that!  You're likely to get something wrong.

Instead, use SSL.  You can use SSL with a server cert and a client cert.  That solves exactly this problem; each party can verify the public key of the other end of the communication and verify they're talking to who they want to talk to.  If everything checks out, they have a secure connection they can use for their communication.  It solves the problem, and it has been vetted far more thoroughly than anything you invent yourself ever will be.


What are the differences between curve NIST P-521 and Edwards E-521 for signature?

What is its signature length ?

Depends on what algorithms you use, but with ECDSA the signature length is twice the length of the order of the base point. For P-521 that's 1042 bits, or 132 bytes when using whole bytes for each part. For E-521 it's 1038 bits or 130 bytes.

  How is it better ?

The design criteria for E-521 are stated in A note on high-security general-purpose elliptic curves:

  The curves Curve25519 and Curve1174 have been engineered to facilitate simple, efficient and secure implementation of general-purpose elliptic curve cryptosystems, with impressive results [8]. On these grounds, it makes sense to look for similar curves at higher security levels.


Having 4096 bit keys and short (< 256 byte) messages, can I simply use the key as OTP?

If your key material is properly random and at least as long as that which is to be encrypted, and indeed each key is used only once, then one-time pad is indeed applicable.

As was noted:

Distribution of keys will be a hard problem. OTP makes practical sense only in scenarios where keys can be distributed at some time T, then used for encrypting and decrypting messages at a later time T', when key distribution would no longer be an option. The red phone used this system (key tapes were exchanged by plane regularly).
OTP does just encryption, not integrity. You probably also need some sort of integrity check, which will need a bit more key material.

You should compute the MAC over the encrypted message, because this obviously prevent any weakness in the MAC algorithm from leaking information about the message. Also, in order to prevent an attacker from swapping messages around, the MAC should probably include a sequence number, or any other unambiguous designation for the key to use (obviously, not a hash of the key).

Alternatively, you can use a MAC over the decrypted message as long as you either encrypt it along with the message, or you use one of these nifty polynomial-based MAC which can be proven not to leak information about what they MAC. If you use OTP, you don't want to lose the psychological benefits of "proven security"...


Does it matter how the IV and XOR are applied for a single AES-128 block?

Yes there are differences.

The first one is identical to CBC mode encryption. CBC requires an IV that is indistinguishable from random to an adversary.

The second is identical to CTR mode encryption where the IV is the initial counter value; the IV only needs to be unique - but the IV can be randomized, as a 128 bit random number is unlikely to repeat.

You never want to do anything to your key other than using it for your cipher. If you want to create multiple keys, use a Key Based Key Derivation Function such as HKDF rather than XOR.

Note that generally you should try and find the best mode for your operation, and only then generate your IV using the rules for that specific mode.

Authenticated encryption using an AEAD cipher such as AES in GCM mode often makes a lot of sense. GCM for instance generally uses a 96 bit IV / nonce instead of a 128 bit IV.


Difference between ε-differential privacy and (ε, δ)-differential privacy

The $\delta$ item is a relaxation of the $\epsilon$-differential privacy notion. The latter is a strong security notion because it requires an algorithm $\mathcal{A}$ to have very close output distributions on "neighbor" datasets $D_1,D_2$ that differ in a single record. From its formal definition

$\Pr[\mathcal{A}(D_1) \in S] \leq e^{\epsilon} \times \Pr[\mathcal{A}(D_2) \in S]$,

we can see that the probability difference should be small for every output set $S$ even if the probabilities $\Pr[\mathcal{A}(D_1) \in S]$ and $\Pr[\mathcal{A}(D_2) \in S]$ are negligible. In other words, such a requirement needs to hold for very unlikely events. Sometimes we want to relax this definition a little bit to cover more general cases as discussed here, so the $\delta$ item is introduced:

$\Pr[\mathcal{A}(D_1) \in S] \leq e^{\epsilon} \times \Pr[\mathcal{A}(D_2) \in S]+\delta$.

This essentially means that those highly unlikely "bad" events happen with probability $\leq\delta$. These "bad" events may break $\epsilon$-differential privacy but are properly bounded.


What NIST protocol was allegedly backdoored by NSA in 2006?

The standard in question was the Dual Elliptic Curve Deterministic Random Bit Generator (Dual_EC_DRBG), standardized in NIST Special Publication 800-90. In this case, it was not a protocol, but instead a random number generator. It wasn't exactly "broken"; instead, it was proven that there existed a "master key", if you will, that would allow someone to predict the stream of "random" bits. (That is, the PRNG isn't really random if you happen to know the proper numbers.)

Despite that the cryptography community has been aware of this for some time now, this discovery has resurfaced in the recent media firestorm surrounding the Snowden leaks. Note that we aren't really sure if the NSA really constructed the backdoor, or if they have the backdoor "key", although recent events seem to suggest that they do.

You can find some more information at these links:

Who uses Dual_EC_DRBG?, a recent question on this site
The Strange Story of Dual_EC_DRBG, a blog post by Schneier on the matter (from 2007, mind you!)

and of course, the citations at the bottom of the above-linked Wikipedia article are always nice to look at.


Security of a block cipher if double encryption $E_{K_2} \circ E_{K_1}$ is always single encryption $E_{f(K_1,K_2)}$

This question was tested years ago by Kaliski at. al Is the Data Encryption Standard a group? (Results of cycling experiments on DES as;

Is DES closed under functional composition?

They applied the cycling test and concluded that DES is not a group. Therefore, we don't expect  that $$\operatorname{DES}(k_2, \operatorname{DES}(k_1, M)) = \operatorname{DES}(k_3, M)$$

As noted in the article, if there was such functional composition then a known-plaintext attack with $2^{28}$ would be able to break DES, on average.


Does Rabin function lose its one-way property if squaring mod a prime?

Would [$f_N(x)=x^2\bmod N$] lose the one-way property if $N$ is prime and not a product of two primes?

Yes, thanks to the Tonelli-Shanks algorithm (special cases here).

[Is] Rabin function still one-way if factorization of $N=pq$ is known?

No, because the main ("only") information advantage the private key holder has in the Rabin cryptosystem over the public key holder is the factorization of $N$. If the one-wayness was preserved even under known factorization the system wouldn't allow decryption in its normal form.
The way to see how factorizing allows square roots in this scenario is to remember that the chinese remainder theorem establishes a ring isomorphism between $\mathbb Z_N$ and $\mathbb Z_p \times \mathbb Z_q$ ... and as established above we know how to compute square roots in $\mathbb Z_p$.


Any shortcut to compute the cipher text for AES applied $n$ times to initial message $m_0$? Or compute $n$ for given $m_0, m_n$?

No, there is no big shortcut possible in practice, as far as we know. One would be a major blow of AES.

A small speedup is pre-computing the subkeys, which saves a small constant factor (like 2) compared to doing that computation on the fly at each iteration. Also, the first and last subkeys can be grouped into one by XOR, saving one 128-bit XOR at each iteration. We could merge the subkeys involved in the AddRoundKey step with tables implementing the SubBytes step, essentially removing AddRoundKey, at the cost of more tables. With dedicated logic, we could bring the time $t$ an iteration takes to few nanoseconds.

IF we first reach $m_i=m_0$ for $i=l<n$, then we know that $m_n=m_{n\bmod l}$ and we have already computed that value. By keeping intermediary values of $m_i$ (say, at regular interval, doubling the interval when we exceed available memory), we can find $m_n$ with little more computations. However, that occurs with probability about $2^{-128}$ for each $l$ with $0<l\le2^{128}$ if we model AES as a random permutation, thus the probability that we can use this shortcut is $\max(1,(n-1)/2^{128})$.

For very large $n$, it is conceivable to parallelize the computation, obtaining the result in sizably less time than $n\;t$. But the expected effort would be in the order of $2^{128}$ AES computations, which is perhaps a million times more than what was wasted so far in bitcoin mining, thus impractically large.

Another thing that we can do, in theory: first reduce $n$ modulo the Least Common Multiple of all possible periods $l$, that is A003418$(2^{128})$. For example, we can state with certainty that for $n=(2^{128})!+42$, we have $m_n=m_{42}$, which is pretty easy to compute. However, any $n$ allowing that shortcut is too large to store as an explicit integer.


Of course not. As long as it is used and - preferably - unbroken, the algorithm is still out there. Actually, it is used a lot in the smart card world and ECDSA certificates are still out there as well. Not all crypto libraries will probably support the newer curves either.

ECDSA is still secure when it is being used correctly. Sure, it is harder to secure but if it is used correctly then nothing short of a quantum computer can break it. It also has quite a few curves defined for it, so there are plenty of (stronger) key sizes allowed.

As far as I know, no standard defining ECDSA or build upon ECDSA has been redacted or withdrawn. You would expect that to happen if it would be considered obsolete / deprecated. If it is the best choice for new protocols is of course up to the designers - I'd probably prefer EdDSA for now.

And if MD5, RC4 and DES / two-key triple DES have taught us anything, it is that algorithms are being used even after they are broken and / or withdrawn. Unfortunately.


How to use HMAC for large ciphertexts over TLS

Well, when TLS encrypts a stream of traffic, it breaks up the data into records.  Each record contains up to 16k of data, and includes its own HMAC.  Hence, there is no HMAC over the entire downloaded file; instead, there are a series of HMACs; every single byte of data is covered by one of those HMACs.


How can I exploit the structure of the secp256k1 prime for fast arithmetic?

Let $p = 2^n - c$.  Then $2^n - c \equiv 0 \pmod p$, so $2^n \equiv c \pmod p$.
 Suppose you have an integer $$x = 2^n x_{\mathrm{hi}} + x_{\mathrm{lo}}.$$  Then $$x \equiv c\cdot x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod p.$$  In other words, you can compute a reduction step by shift/multiply/add: shift right by $n$, multiply by $c$, and add to the low $n$ bits.

The best case is when $c = 1$, so $p$ is a Mersenne prime: then you can skip the multiplication altogether.  But you can generalize this further for $p = 2^n - 2^m - d$, since $2^n \equiv 2^m + d \pmod p$, so $$2^n x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv 2^m x_{\mathrm{hi}} + d \cdot x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod p.$$  That is, you can compute a reduction step by an $n$-bit shift, an $m$-bit shift, a multiply by $d$, and two adds.

Similarly, if $p = 2^{2m} - 2^m - 1$, like Ed448-Goldilocks uses, then you can compute a reduction step $$2^{2m} x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv 2^m x_{\mathrm{hi}} + x_{\mathrm{hi}} + x_{\mathrm{lo}}$$ with two $n$-bit shifts and two additions.

Obviously, you can always write any modulus as a sum of powers of two; the more terms there are, the more costly the reduction step is to write as a series of shifts and adds.  In software implementations, at some point it may be faster to use the CPU's multiplier than your own shift-and-add steps.  For instance, in secp256k1, I'd guess that it is fastest to write it as $2^{256} - 2^{32} - 977$ if you can take advantage of a CPU's 32x32->64-bit multiplier, but you should consult libsecp256k1 for the state of the art in arithmetic modulo this prime.


[This incomplete answer is a community wiki; fell free to expand/correct it]

The self-shrinking generator, and von Neumann de-biasing applied to the output of an LFSR, both group bits output by the LFSR in pairs, and for each pair output either nothing or a single bit, according to this table:

Pair    SSG    VN
 00      -     -
 01      -     0
 10      0     1
 11      1     -

We hereafter assume the LFSR has $n$ bits and is maximum-length (that is, uses a primitive polynomial and is not initialized to all-zero).

The LFSR has period $2^n-1$, and within that each of the pairs 01, 10, and 11 appears exactly $2^{n-2}$ times, while the pair 00 appears $2^{n-2}-1$ times. If follows that in $2^{n+1}-2$ steps of the LFSR, both the SSG and VN output exactly $2^{n-2}$ times 0 and as many times 1, and cycle.

Thus both the SSG and VN cycle after (at most) $2^{n-1}$ outputs, and have no bias. For $n>3$, the shortest period conjecturally is $2^{n-1}$ (that conjecture was made for the SSG by Willi Meier and Othmar Staffelbach's The self-shrinking generator, in proceedings of Eurocrypt 1994; they give proof that the shortest period is at least $2^{\left\lfloor n/2\right\rfloor}$).

Illustration with 2 periods of 31 steps of the LFSR based on $x^5+x^2+1$: both SSG and VN have period 16, with 8 zeroes and 8 ones.

LFSR 10101110110001111100110100100001010111011000111110011010010000
SSG   0 0 1 0 1     1 1   1     0         1   0   1 1 0   0 0
VN    1 1   1     0         0   1   0 0 0   0 1       1 0 1 1 0


Would knowing the random seed help to break AES or similar?

Yes, it can hugely help. There are many examples, but the DUHK attack is as good as any. This allows you to passively attack cryptosystems with the following characteristics:

  It uses the X9.31 random number generator
  The seed key used by the generator is hard-coded into the implementation
  The output from the random number generator is directly used to generate cryptographic keys
  At least some of the random numbers before or after those used to make the keys are transmitted unencrypted. This is typically the case for SSL/TLS and IPsec.

The reason it is specific to the X9.31 PRNG can be found here (in short, X9.31 has a "long term seed key").
The idea is that if you know the long term seed key, and see some direct output (the 4th assumption), you could recover the state of the PRNG, which is then sufficient (via the 3rd point) to recover the generated cryptographic keys.

Heuristically, if your PRNG starts with too little entropy, the outputs of it are "less random" than other parts of the protocol assume, which can break the other parts of the protocol.

As for how devices generate random seeds, they typically poll a system RNG (typically /dev/urandom/ on UNIX devices). How does /dev/urandom/ generate random numbers?
From the environment (see here for some discussion). I do not know what is currently used in each device/OS, but generally (theoretical) cryptographers mention things like:

Measuring temperature fluctuations on the CPU
Measuring timings on various input devices (keyboards/mice), and in general other "random" information from external devices

These may not all be used in practice, but give some intuition for what "random sources" a device may have available to it.
Note that certain devices (say embedded devices) may have less sources available --- this has led to attacks on embedded systems. A followup paper to an attack. This paper includes the following motivation of their work:

  Motivation: Our work is inspired by the recent paper of
  Heninger, Durumeric, Wustrow, and Halderman [16], which
  uncovered serious flaws in the design and implementation of
  the Linux kernel’s randomness subsystem. This subsystem
  exposes a blocking interface (/dev/random) and a nonblocking interface (/dev/urandom); in practice, nearly
  all software uses the nonblocking interface. Heninger et al.
  observe

  that entropy gathered by the system is not made
  available to the nonblocking interface until Linux estimates
  that 192 bits of entropy have been gathered, and
  that
  Linux is unnecessarily conservative in estimating the entropy
  in events, and in particular that on embedded systems no
  observed events are credited with entropy.

  These two facts
  combine to create a “boot-time entropy hole,” during which
  the output of /dev/urandom is predictable.

  The Linux maintainers overhauled the randomness subsystem in response to Heninger et al.’s paper. The timing
  of every IRQ is now an entropy source, not just IRQs for
  hard disks, keyboards, and mice. Entropy is first applied to
  the nonblocking pool, in the hope of supplying randomness
  to clients soon after boot. (Clients waiting on the blocking
  interface can block a bit longer.)

Note that the Heninger et al attack mentioned was the Mining your P's and Q's attack, which was an attack on RSA.
RSA has a public key which contains $n_i = p_iq_i$, the product of two semiprimes.
The attack essentially collected many $n_1,\dots, n_k$ RSA moduli, then searches (pairwise) for common divisors among all of them (which can be made quite efficient).
Any such common divisor allows you to factor two moduli.
If PRNGs were working properly then the theory behind this predicts this will fail.
This attack exposed that the PRNGs were not working properly, due to insufficient entropy early in the boot process in embedded devices.

Note that "insufficient entropy" can be viewed as "having some partial information about the seed". Knowing the seed completely is an extreme example of this, and while this won't necessarily mean every cryptosystem breaks, many break from weaker assumptions.


What is the key strength reduction encrypting only 160 bits of data using RSA1024 for signatures?

Well, there are no necessary 'reduction in strength', for two reasons:

You ask about how many signatures you'd need to recover the private key.  Well, even with unrestricted Oracle access to the private operation, there's no known way to recover the private key (or equivalently, factor the modulus) that's more efficient than just ignoring the Oracle and attacking the modulus directly.  Hence, giving the attacker access to a limited number of signatures cannot help him recover the private key.
What the attacker might be able to do with some padding methods is deduce the value of other signature operations; this would be generating a forgery without the private key.  Now, there are certainly known padding methods (such as a naive 'zero fill' method) that are prone to this.  On the other hand, there are deterministic padding methods (such as the PKCS #1.5 RSASSA-PKCS1-v1_5 method) for which there is no known method of generating forgeries easier than finding collisions in the hash function.

So, if the system is using, say, the above PKCS method, there is no known weakness, even if the attacker has access to huge numbers of signatures.


Is there an algorithm to find the number of intersections of two sets?

Answer. Yes!  It is possible to do this, using the magic of secure multi-party computation.  The security property we get is basically the best one could possibly hope for: namely, your friend learns nothing more about your set of numbers than the maximum he could have learned by choosing his set in a clever way and learning the size of the intersection; and your friend gets symmetrical protection against you.

The particular problem you list is known as the cardinality set intersection problem or cardinality private set intersection problem, and there has been considerable research on protocols for this problem.

One way to solve this problem is using the standard general-purpose machinery for secure two-party computation.  The general-purpose tools for secure two-party computation can be applied directly to this problem, giving one way to do what you want.

Alternatively, researchers have devised special-purpose protocols designed especially to solve the cardinality set intersection problem.  These special-purpose protocols are considerably more efficient than what you get if you apply the general-purpose methods.  Here are some some pointers into the research literature in this area:

Lea Kissner, Dawn Song, Privacy-Preserving Set Operations, CRYPTO 2005.
Yingpeng Sang, Hong Shen, Efficient and Secure Protocols for Privacy Preserving Set Operations, ACM TISSEC 2009.  (Improves upon Kissner-Song.)
Michael J. Freedman, Kobbi Nissim, Benny Pinks, Efficient private matching and set intersection, EUROCRYPT 2004.  (An alternative to Kissner-Song.)
Carmit Hazay, Kobbi Nissim, Efficient Set Operations in the Presence of Malicious Adversaries, PKC 2010.  (Improves upon Freedman-Nissim-Pinks in the malicious model.)
Dana Dachman-Soled, Tal Malkin, Mariana Raykova, Moti Yung, Efficient Robust Private Set Intersection, ACNS 2009.  (Addresses the malicious model.)

Mathematical details. Here's the basic idea behind Kissner and Song's approach:

They encode each set as a polynomial: for example, the set $S = \{3,5,17\}$ is encoded as the polynomial $s(x) = (x-3)(x-5)(x-17)$, the set $T = \{4,12,17\}$ is represented as $t(x) = (x-4)(x-12)(x-17)$, and so on.  In general, a polynomial $p(x)$ represents the set of roots of $p(x)$, i.e., the set $\{a : p(a)=0\}$.
Given polynomials $s(x)$,$t(x)$ representing the sets $S,T$, we can compute a polynomial $u(x)$ representing the intersection $U = S \cap T$, by picking random polynomials $q(x),r(x)$ and computing

$$u(x) = q(x)s(x) + r(x)t(x)$$

Note that the roots of $u(x)$ are (with high probability) exactly the common roots of $s(x)$,$t(x)$, i.e., $u(a)=0$ usually happens only when $s(a)=t(a)=0$

For example, if with sets $S,T$ defined as in 1 above, we might pick $q(x) = 2x^3 + 7x^2 + x - 3$ and $r(x) = 14x^3 + 3x^2 - 2x + 5$.  Then we can calculate $u(x) = 16 x^6 - 502 x^5  + ... - 3315$, whose only integer root is $x=17$.  This corresponds to the fact that $U = S \cap T = \{17\}$.
They use Pallier's additively homomorphic public-key encryption scheme.  In particular, you and your friend jointly generate a Paillier public/private keypair, so that both of you know the public key but the private key is shared between you (it is only possible to decrypt if both of you jointly participate).  There are known ways to do this.
You take your set $S$, encode it as a polynomial $s(x)$, and encrypt each coefficient under the Paillier public key, and send the resulting encrypted polynomial to your friend.  Your friend takes his set $T$, encodes it as a polynomial $t(x)$, encrypt each coefficient under the Paillier public key, and send the resulting encrypted polynomial to you.  You jointly generate random polynomials $q(x),r(x)$ (there are known ways to do this).  Then, using the additively homomorphic properties of Paillier encryption, you can both compute an encrypted form of the polynomial $u(x) = q(x)s(x) + r(x)t(x)$, where you get the encrypted value of each coefficient of $u(x)$.  You each share the value of $u(x)$ you got with the other person.
For each element $a$ of your set $S$, you evaluate the encrypted polynomial at $a$, thus learning the encryption of $u(a)$, call it $E(u(a))$ (the additively homomorphic properties of Paillier encryption allow you to do this), and then you pick a random non-zero value $c$ and multiply to get $E(c*u(a))$.   You do this separately for each element of your set, so you get $|S|$ encrypted values, you shuffle them, and send them to your friend.  Your friend does the same with his set and sends you a shuffled set of $|T|$ encrypted values.

In the running example, you'd learn the encryption of $u(3)$, $u(5)$, and $u(17)$, you'd pick random non-zero values, say $8$, $2$, $5$, and you'd share $E(8\cdot u(3))$, $E(2\cdot u(5))$, and $E(5 \cdot u(17))$ with your friend in random order.  In this case $u(3)=-50904$, $u(5)=152880$, $u(17)=0$, so you'd be sharing $E(8\cdot-50904)$, $E(2\cdot152880)$, and $E(0)$, in random order. Your friend would do something similar with his set.
Finally, you and your friend jointly decrypt the encrypted values you've shared with each other, using the shared private key.  You count how many zeros you see in the decrypted values your friend sent you.  Your friend counts how many zeros are present in the decrypted values you sent him.  This is the number of values you had in common, i.e., the cardinality of $|S \cap T|$.

I've introduced some simplifications (e.g., all computations have to be done in an appropriate group, and many others).  Please don't try to implement based upon this description alone.  See Kissner and Song's paper for the full details.  You might also look into the subsequent literature; there have been some follow-on papers that claim to improve their scheme to get better performance, though I'm not familiar with all the details.  Also, in a real implementation, you'd need to add some zero-knowledge proofs at each step, to prove that each participant correctly performed their own computation (i.e., to lift from the honest-but-curious model to the malicious model).  There has been follow-on research on that problem as well.

Summary. As you can see, this gets highly technical -- but the bottom line is that this problem has been studied in detail before, and there exist clever, beautiful, efficient solutions to it.


Should I use RSA encryption since RSA is said to be broken by NSA?

This question has many problems in the way it was asked, and clearly did not come after doing some investigation. However, since this seems to be a misconception that is spreading widely, I will relate to it.

It is not true that the "crypto community" (whoever that is) believes that the NSA can break RSA. In fact, if Snowden taught us anything, it is that the NSA is using many techniques to bypass RSA in TLS and elsewhere (stealing private keys, utilizing implementation bugs, and more), but are not breaking RSA. If they could break RSA then this wouldn't be necessary and would be the easiest route to take.

Now, it may very well be that the NSA has some advantages in factoring over the academic and open crypto community. This makes a lot of sense for two reasons:

We share everything that we discover with them (by publishing papers), and they share nothing about what they discover with us
They have absurd computing power that they can utilize

Having said the above, I do not think that they can do much more than the rest of us. What's my basis for this belief? Nothing except that many very strong academic minds have also worked on this, and the Snowden revelations about what they are doing.

This possibly justifies the move to RSA-2048 (instead of settling on RSA-1536). I am very skeptical that the NSA can go beyond RSA-1024 by much. However, I think that it is a good idea to use RSA-2048 because I strongly believe that this is way beyond their power, again for the reasons stated above.


Yes, you got the scheme essentially right - except that the group cannot be $\mathbb{Z}_p^*$, as the latter does not have prime order. It can however be many other things - like the multiplicative subgroup of squares over $\mathbb{Z}_p^*$, or an elliptic curve. Let us simply consider the scheme as you described it, over some group $\mathbb{G}$ of prime order $p$.

Why is the scheme hiding?

Intuitively, the scheme is perfectly hiding because for any commitment $c$, and for any tuple $(m_1, \cdots, m_n)$, there exists an opening $r$ that "explains" $c$ as $c = y^r\prod_{i=1}^n g_i^{m_i}$, and the distribution of this $r$ (taken over the coins used to generate $c$) is uniform.

More formally, denoting $a\gets_r S$ the action of drawing $a$ uniformly at random from $S$, the commitment scheme is perfectly hiding because for any pair of tuples $(m_1, \cdots, m_n)$ and $(m'_1, \cdots, m'_n)$, the distributions $$D = \left\{c : r\gets_r\mathbb{Z}_p, c \gets y^r\prod_{i=1}^n g_i^{m_i}\right\} \text { and } D' = \left\{c : r\gets_r\mathbb{Z}_p, c \gets y^r\prod_{i=1}^n g_i^{m'_i}\right\}$$ are perfectly equal. This is easy to show: for $i=1$ to $n$, let $\alpha_i$ denote the exponent of $g_i$ in base $y$ (id est, $g_i^{\alpha_i} = y$). Let $\alpha \gets \sum_{i=1}^n \alpha_im_i$ and $\alpha' \gets \sum_{i=1}^n \alpha_im'_i$.

Then $c$ is computed as $y^r\prod_{i=1}^n g_i^{m_i} = y^{r+\alpha}$ in $D$ (for a random $r$), and as $y^r\prod_{i=1}^n g_i^{m'_i} = y^{r+\alpha'}$ in $D$ (for a random $r$). The equality of the distributions is therefore immediate.

Why is the scheme binding?

We can show that the scheme is binding under the discrete logarithm assumption. Let $\mathcal{A}$ be a PPT adversary which, given the parameters of the system (in this case, $(y,g_1, \cdots, g_n)$) can produce (with non-negligible probability $\varepsilon$) a commitment together with valid openings to two different plaintexts, id est: $(c,(m_1, \cdots, m_n),r,(m'_1,\cdots, m'_n),r')$, where $c\in\mathbb{G}$ is a commitment, $(m_1, \cdots, m_n) \neq (m'_1, \cdots, m'_n)$, and $$c = y^r\prod_{i=1}^n g_i^{m_i} = y^{r'}\prod_{i=1}^n g_i^{m'_i}.$$

Let us use this algorithm to break the discrete logarithm assumption with non-negligible probability. Upon receiving a random discrete-log challenge $(g,y)$, we pick $i$ at random between $1$ and $n$, and set $g_i \gets g$. Then we pick $n-1$ values for $\alpha_j$, $(\alpha_j)_{j\neq i}\gets_r \mathbb{Z}_p^{n-1}$ and set $g_j \gets y^{\alpha_j}$ for any $j\neq i$. Observe that $(y, g_1, \cdots, g_n)$ is perfectly distributed as a valid tuple of parameters for the Pedersen commitment scheme. Therefore, we run $\mathcal{A}(y,g_1,\cdots, g_n)$ and obtain $(c,(m_1, \cdots, m_n),r,(m'_1,\cdots, m'_n),r')$ where it holds with probability $\varepsilon$ that $(m_1, \cdots, m_n) \neq (m'_1, \cdots, m'_n)$ and $c = y^r\prod_{j=1}^n g_j^{m_j} = y^{r'}\prod_{j=1}^n g_j^{m'_j}$. We check whether $m_i \neq m'_i$, and restart the protocol otherwise. Note that as our (uniformly random) choice of $i$ is perfectly hidden from $\mathcal{A}$, and as $(m_1, \cdots, m_n) \neq (m'_1, \cdots, m'_n)$ with probability at least $\varepsilon$, it holds that $m_i \neq m'_i$ with probability at least $\varepsilon/n$.

Let $\alpha \gets \sum_{j\neq i} \alpha_j m_j$ and $\alpha' \gets \sum_{j\neq i} \alpha_j m'_j$. If $m_i \neq m'_i$, we therefore have the following:

$y^r\prod_{j=1}^n g_j^{m_j} = y^{r'}\prod_{j=1}^n g_i^{m'_j}$

hence $y^r g^{m_i}\cdot y^{\alpha} = y^{r'} g^{m'_i} y^{\alpha'}$

hence $y^{r-r'+\alpha-\alpha'} = g^{m_i-m'_i}$, with $m_i - m'_i \neq 0$

hence $y^{(r-r'+\alpha-\alpha')\cdot(m_i-m'_i)^{-1}\bmod p} = g$: we obtain the discrete log of $y$ in base $g$.

Therefore, if $\mathcal{A}$ breaks the binding property of the Pedersen commitment scheme with probability at least $\varepsilon$, we can construct an algorithm which, given access to $\mathcal{A}$, extracts the discrete logarithm of $g$ in base $y$ with probability at least $\varepsilon/n$.


Using a mono-alphabetic substitution cipher with a different language per word

This is a lossy algorithm. You will lose information during the translation and reverse-translation steps. Introducing loss into any algorithm obviously increases the difficulty in pulling the clean plaintext out, since it's potentially impossible to pull the clean plaintext out even with the key.

Even so, fairly normal cryptanalysis should apply here. You just need to use a multi-language frequency table. I assume that all languages involved will use a single alphabet? You would drop accents from languages that have them? This is no different than the common step of merging "I" and "J" in ciphers. If you rely on Romance languages, cognates would hurt you. If you go beyond Romance languages, then you're faced again with possibly lossy transliteration, particularly if you mix in Asian or Middle Eastern languages.

This is not dramatically different than the common technique of intentional misspellings. Take a look at Kryptos for a very advanced example that involves the kind of complications you have in mind.

I'd say that your idea makes analysis harder, but not fundamentally different.

When you make this a non-lossy translation, you're describing a homophonic cipher. A book cipher is an example. The idea is that you have different symbols representing the same letter or word. In your case, you're replacing the symbol "road" with either the symbol "rue" or the symbol "camino" or the symbol "lu" for example. You are then applying an alphabetic cipher to the result. This has been used for a several hundred years to prevent frequency analysis. Look at the Great Cipher for a sophisticated version of this approach. Note that as you've describe it, I strongly doubt you'd be able to devise a group of languages that resisted frequency analysis. You'd eventually have to start creating more random symbols (words) until this looked very unlike the original design in my estimation.


Why don't I see the IV in the FINISHED fragment in TLS_RSA_WITH_AES_256_CBC_SHA communication with OpenSSL?

Nothing is wrong, it is just that when decrypting CBC cipher text, the IV will only affect the decryption of the first block. The first cipher text block will be used as IV when decrypting the second cipher text block, the second cipher text block will be used as IV when decrypting the third cipher text block, etc.

Consequently, if the IV is prepended to the CBC cipher text, you may actually use any arbitrary IV you want when decrypting the cipher text, as long as you "decrypt" the IV as well and discard the first block of decrypted text prior to presenting the plain text to the next layer.

Hence, none of the information you provide in your question is inconsistent with the cipher text fragment really being a GenericBlockCipher.

Also note that in TLS 1.2, the IV of a GenericBlockCipher fragment will typically be generated randomly. In particular, it must not be identical to the IV optionally generated by the KDF in TLS 1.0 compatibility mode.


The idea of a counter stream mode of AES is to generate an random stream of bits by chunk of 128 bits but you are not forced to use all the 128 bits of it.

To encrypt the process is the following, considering $m$ the 64 bits message :

Generate $s = AES(Key, Nounce)$
Notice that $s$ is 128 bits long so $s = s_1 || s_2$ where $s_1$ and $s_2$ are 64 bits long.
$c = m \oplus s_1$ and drop $s_2$ (useless)

To decrypt the process is the same:

Generate $s = AES(Key, Nounce) = s_1 || s_2$ where $s_1$ and $s_2$ are 64 bits long.
$m = c \oplus s_1$

Even though I provided you an answer from a Crypto point of view, I consider this question as off-topic as it feels more like it requires a code answer rather than a Crypto answer (more math oriented).


For ElGamal-based key encapsulation, is it necessary to hash before using as AES key?

The issue here was that the hashing is used to derive an AES key for encryption from the value $m$ in the question. However, it is still the value of $m$ that needs to be encrypted using the public key and the homomorphic ElGamal algorithm, not $H(m)$. After homomorphic decryption the value $m'$ can be retrieved, and $H(m')$ will create the same AES key to be used to decrypt the message iff $m' = m$.

The idea of the hash is to compress the entropy in $m$ so that the (leftmost bytes) of the result can be used as a well distributed AES key.

Even more information and the road towards this answer can be found in the comments below the question and the chat.


Can an RSA encrypted message be altered?

Close; what would work would be if Eve encrypts 2 with the public key (forming $2^e \bmod N$), and then multiplies the ciphertext ($P^e \bmod N$ with that.  When Alice decrypts it (by raising it to the power of $d$, she'll compute:

$$(2^e \times P^e)^d = 2 \times P$$

which is what Eve wants.

On the other hand, this is assuming that Alice uses raw RSA, without padding.  When you add in padding (which any sane use of RSA encryption should use), this doesn't work.


AES is a block cipher, a cryptographic primitive. It has no involvement with key derivation or anything of that nature. The three standard key sizes are 128 bit, 192 bit, and 256 bit. How you get those keys is beyond the purview of AES, which is concerned only with encryption. As I said, it is a cryptographic primitive, meaning it is meant to be used in a larger system (usually). In fact, "AES" itself can't encrypt more than one block of data; to do that, you need to use a block cipher mode of operation. I'd recommend, for non-authenticated schemes, either CTR or CBC, not ECB. But in general, you probably want one of the authenticated modes (AEAD), like GCM, OCB, EAX, or CCM.

So, the fact that OpenSSL lets you use a passphrase is entirely unrelated to AES. Typically, I would recommend against using passphrases for encryption, as they are notoriously low-entropy and vulnerable to simple guessing. OpenSSL does use a salt by default, which improves things, but the algorithm it uses is "somewhat" questionable. The default hash function used in it is MD5, and it only uses just a few rounds by default. So, if possible, I would very highly recommend you generate a real key instead of using a passphrase. And, like your question implies, if the adversary knows your file is encrypted with a passphrase, it makes using a larger key sort of moot.

Just remember that AES was designed as a block cipher, so the whole passphrase business is really separate from it. Anyway, if you are interested in the practical differences in AES-128, AES-192, and AES-256, there are several good questions on this site with good answers:

What are the practical difference between 256-bit, 192-bit, and 128-bit AES encryption?
What is the effect of the different AES key lengths?
Is AES-256 a post-quantum secure cipher or not?