If we have multiple unique RSA signed messages produced from the same private key, can we always find new valid signatures? Say Alice publishes $t$ unique signed messages with her private key $d$,
$$
m_1^d, m_2^d, m_3^d, ... , m_t^d \mod n
$$
For $t = 2$, we have $m_1^d, m_2^d \mod n$ and if we let $x \equiv m_1m_2 \mod n$ then we can produce a valid signature,
$$
x^d \equiv (m_1m_2)^d \equiv m_1^d\times m_2^d \mod n
$$
For $t$ signatures, I think we can have at most $\sum_{i=2}^{t}\binom{t}{i}$ new signatures. Is this correct?
This was inspired by a quiz question in which Alice published $t$ RSA signatures and we were asked to find a valid signature for $M \equiv m_1^{-1} \times m_2^{-1} \times m_3^{-1} \times ... \times m_t^{-1} \mod n$ and the solution was,
$$
M^d \equiv (m_1^{-1} \times m_2^{-1} \times m_3^{-1} \times ... \times m_t^{-1})^{d}
\equiv (m_1^{d} \times m_2^{d} \times m_3^{d} \times ... \times m_t^{d})^{-1} \mod n
$$
We assumed that all inverses existed. So, I was wondering why did this question involve inverses? Are they necessary to produce new signatures? Because as I showed above, I don't see why we could not do that otherwise.

For $t$ signatures, I think we can have at most $\sum_{i=2}^{t}\binom{t}{i}$ new signatures. Is this correct?

That's the number of new (message, signature) pairs with message of the form $\prod m_i^{k_i}\bmod n$ with $k_i\in\{0,1\}$ and $1<\sum k_i$; that is, we combine at least two existing messages. BTW, that simplifies to $2^t-t-1$.
But we can just as well compute the signature for message $\prod m_i^{k_i}\bmod n$ for any integers $k_i$. As noted in the question, $k_i=-1$ or more generally negative works too. And even more generally, we can compute as many (message, signature) pairs as we see fit if we know $(n,e)$, for we can find the message matching any desired signature, by raising the signature to the power $e$ modulo $n$. Problem from an attacker's perspective is that the messages thus obtained are largely random-like.
Conclusion: textbook RSA signature can be secure only if the parties that verify are selective in the messages they accept, and the signers selective in the messages they sign. That's where message padding for RSA signature comes to play.

Are inverses necessary to produce new signatures?

No. That's one of the tricks that can be pulled to form new (message, signature) pairs with specific properties of the message in attacks against some RSA signature practices.


What format should a salt be when it is concatenated with the password? Assume that, in the available environment, it is not possible to use modern password hashing functions (bcrypt, scrypt, Argon2, PBKDF2, etc.), so it is necessary to roll my own stand-in, until they become available. (Or call it a theoretical question, because either way I'll learn something from your answers.)

With a simple (uniterated) SHA256 of the password and a random 256-bit salt, when concatenating the salt and password, is it better to use the binary form of the salt, or is a base64 representation just as secure?

For example, with the salt, hard-wired to 256 bits, it will always end in a '=' in base64 (if the extra character isn't dropped). That seems like it's not ideal.

(Assume the salt is stored with the hashed password, both as base64, so concatenation is easy with that form.)

I Googled and searched here, without much that seemed related to the specific format of the salt when it's being concatenated. This question mentions a length extension attack, which I would think might be easier with the textual base64 salt. (Oh, and this question talks about nested hashes to address the length extension attack as well, but that doesn't seem to apply? and doesn't address the salt format.)

Is the salt format moot because the entropy of 32 binary bytes is the same as 42.7 base64 characters, or is one format really a better choice?

Is the salt format moot because the entropy of 32 binary bytes is the same as 42.7 base64 characters, or is one format really a better choice?

TLDR: moot, for the reason stated, as long as the whole thing is hashed and not otherwise used, and the hash used is secure, and the iterated hash construction on top of that is otherwise sound.

The fear that hashing constant bytes like =, or hashing characters from a reduced set such that of Base64, or hashing more bytes, could cause a cryptographic issue like a loss of entropy or increased risk of collision, is unfounded as long as all the data enters a good hash like SHA-256, and is not otherwise used: the loss of entropy, if any, is computationally undetectable. If it was, it would allow to distinguish the hash from a random function¹. Even though SHA-1 and MD5 are broken, they are sill safe from such problem, thus we can be quite confident about this for the stronger SHA-256.

Introducing a binary-to-text transformation (e.g. Base64) as a pre-processigng of the salt:

Slow downs the function, and that slow down benefits the attacker (which will perform the transformation only once in a password search attack). But for a well-parametrized function, that slowdown is negligible.
Increases the length of the salt as effectively used (at least it should: again truncation would be bad). If the salt was repeatedly hashed in the iterated hash (wjich is possible but not usual), that may slow down the iterated hash sizably (especially if the transformation reaches a threshold requiring more compression rounds per iteration), both for the attacker and legitimate user, thus

if the number of iterations is kept identical, the binary-to-text transformation will make the iterated hash slower, thus safer, but more costly for the legitimate user.
if the number of iterations is adjusted for constant duration, then there will be less difference in security (and we can't tell in which direction)

There can be other side effects. For example, when the key input of HMAC-SHA-256 (a common building block in iterate hash function) exceeds 64 bytes, that key is replaced by its 32-byte SHA-256 hash, requiring at least two extra compression rounds. Thus adding one byte to the key input can abruptly increase duration (and reduce the entropy from up to 512 bit to less than 256, but it's not a worrying security issue).

Notice that since Colin Percival's Stronger Key Derivation via Sequential Memory-Hard Functions (presented at BSDCan 2009), a decent iterated password hashing function must use sizable RAM memory, and ideally be memory-hard (that is, massively parallel implementation should require that same sizable amount of memory for each instance running). It considerably raises the cost of a password search setup, because RAM is expensive, and thus make iterated password hashes sizably more secure. Nowadays, using constructions that require little RAM, like PBKDF2, is either incompetent, or a deliberate way to make the system breakable by well-funded attackers, who can use ASICs to outrun legitimate users by a very large factor.

¹ Modern hashes are expected to be undistinguishable from a random function. SHA-256 is believed to match this except for its length-extension property, and there's reason to believe that it is not an issue in the context.


How can I prevent a message replay with RSA? I am using RSA to encrypt some data but I would like to eliminate the possibility of message replay. By message replay I mean sending a valid message multiple times to the original recipient. It is obvious that an attacker can capture a valid message without knowing its contents and replaying it.

Is there any efficient way for the recipient to determine if a given message has been replayed or avoid the problem altogether?

The only things I can think from the top of my head are: including an expiration time in the message (rather insecure) or hashing the message, storing it and checking if future messages have the same hash value (can consume a lot of memory).

You could use some combination of:

an expiration timeout (i.e. if the message does not arrive until the timeout, we don't accept it)
storing previous values of a nonce.

You only have to store those nonce values whose timeout didn't yet expire.

If the messages arrive all in order, you can instead use a simple counter (which always goes up) and reject every message which has a counter value smaller or equal than the last received one.


Likelihood of signature collision with EdDSA Taking EdDSA as an example, given the length of a signature is 512-bits for a given data payload,
what is the probability of a collision where there is another 512-bit value that is also a valid signature?
With symmetric crypto we know there is only one single key in the entire space that will validly decrypt data encrypted with the same key.
Can we provably state that for a given payload and given private key, there is only one valid signature in the 512-bit signature space? That is, no other signature exists that could be validated with the public key counterpart to the private key that created the signature.

Can we provably state that for a given payload and given private key, there is only one valid signature in the 512-bit signature space?

No.
If you consider EdDSA verification a legitimate signer can generate more than one signature of a given message, and all will pass EdDSA verification.
However, only the signature generated with the EdDSA signing procedure will pass cofactorless verification.
More details about how to generate alternative valid signatures are provided in this answer.
Regarding the more broader question:

Taking EdDSA as an example, given the length of a signature is
512-bits for a given data payload, what is the probability of a
collision where there is another 512-bit value that is also a valid
signature?

Requiring specifically to pass cofactorless verification only (to avoid the other valid signatures generated by the above technique), there should be a valid $S$ for each possible value of $r$. Since $R$ depends fully on $r$, and $0 \le r < L$, there are at least $L$ possible valid signatures, where $L$ is the order of the large prime subgroup. For ed25519, $L = 2^{252}+27742317777372353535851937790883648493$


Issue with decrypting self-coded AES Summary: As a trainee, I got the task to extract encrypted passwords of our external password manager (Zoho Vault) and decrypt them. The documentation regarding how to decrpyt them is...none. I ask the support for help, but they send me only some pages of their documentation...
Research and attempts:
According of my account and the documentation of Zoho Vault API, the algorithm is a "PBKDF2_AES". I used at first the PBKDF2 encryption to generate a key, by using a passphrase + a salt + an iteration of 1000, which I received with some API calls. Next, I tried to use the Zoho Vault decrypting function (which decrypts AES encryptions), but I didnt got the result I wanted. After that, I checked an Online AES Encrypter/Decrypter and tried my luck there. After filling the forms with all the required info, I received an error. Just to be sure, that it was the right encrypt/decrypt method, I encrypted some other example data and the result had the same Base64 pattern password I tried to encrypt. After I checked the "PBKDF2 generated key" and mine. The one I made was for a AES-256. But the "PBKDF2 generated key" seems to be 64 byte long/AES-512.
Which I did some research and it almost seems it doesnt exist.
I just cant figure out how to continue...
If needed, I can share all required keys and encrypted data, since they are all dummies for the later used account anyway.

But the "PBKDF2 generated key" seems to be 64 byte long

Sounds like the algorithm is actually PBKDF2-SHA512 or some other 512-bit has function, as PBKDF2 does NOT use AES as its PRF. Generally this is truncated down to 256 bits to use with your block cipher. I would check what you are using as the PRF, try replicating the master key by choosing different 512-bit hash functions until you get a match, then work onto decryption after.


Is whirlpool vulnerable to length extension attack? Is whirlpool vulnerable to length extension attacks?
I did not find anything on the topic and hardly anything interesting about whirlpool at all. I am trying to build some HMAC for a program and consider using whirlpool to do so.

Let's split your question into two parts: first the length extension attack problem with Whirlpool, and next your HMAC tool idea.

1. Is whirlpool vulnerable to length extension attack?

Yes, Whirlpool by itself (as a plain hash, not HMAC) is indeed vulnerable to length extension attacks.

Besides Crypto.SE Q&As like “Understanding the length extension attack”, the SkullSecurity.org website offers an explanation in their article “Everything you need to know about hash length extension attacks”. Here's an excerpt:

  The attack

  An application is susceptible to a hash length extension attack if it prepends a secret value to a string, hashes it with a vulnerable algorithm, and entrusts the attacker with both the string and the hash, but not the secret. Then, the server relies on the secret to decide whether or not the data returned later is the same as the original data.

  It turns out, even though the attacker doesn't know the value of the prepended secret, he can still generate a valid hash for {secret || data || attacker_controlled_data}! This is done by simply picking up where the hashing algorithm left off; it turns out, 100% of the state needed to continue a hash is in the output of most hashing algorithms! We simply load that state into the appropriate hash structure and continue hashing.

  TL;DR: given a hash that is composed of a string with an unknown prefix, an attacker can append to the string and produce a new hash that still has the unknown prefix.

  Example

  Let's look at a step-by-step example. For this example:

let secret = "secret"
let data = "data"
let H = md5()
let signature = hash(secret || data) = 6036708eba0d11f6ef52ad44e8b74d5b
let append = "append"

  The server sends data and signature to the attacker. The attacker guesses that H is MD5 simply by its length (it's the most common 128-bit hashing algorithm), based on the source, or the application's specs, or any way they are able to.

  Knowing only data, H, and signature, the attacker's goal is to append append to data and generate a valid signature for the new data. And that's easy to do!

In that article, they also link to a tool which allows to practically do a length-extention attack on every algorithm you could wish for – including WHIRLPOOL.

The tool – coded in plain C – is available for free and hosted at Github under the name hash_extender. Quoting its description, hash_extender…

  … implements a length extension attack against every algorithm I could think of:

  MD4
  MD5
  RIPEMD-160
  SHA-0
  SHA-1
  SHA-256
  SHA-512
  WHIRLPOOL

  I'm more than happy to extend this to cover other hashing algorithms as well, provided they are "vulnerable" to this attack -- MD2, SHA-224, and SHA-384 are not. Please contact me if you have other candidates and I'll add them ASAP!

2. I am trying to build some HMAC for a program and consider using whirlpool to do so.

This again lifts the length extension attack problem described above, since a HMAC construction (which securely hashes data with a secret key) prevents length extension attacks. For details on how a HMAC construction achieves that, you can check the Crypto.SE Q&A “How does the secret key in an HMAC prevent modification of the HMAC?” which explains that HMACs were designed to void length extension attack issues.

When trying to attack a HMAC,

  …the attacker only controls variable-length input to the inner hash, not the outer hash…

So, the answer which practically considers your question title as well as your description is extended to:

Yes, Whirlpool by itself (as a plain hash, not HMAC) is indeed vulnerable to length extension attacks – but since you plan to use it in a HMAC construction (which prevents length extension attacks) you can safely ignore that attack vector. Yet, it should be noted that I'm assuming you implement the HMAC construction correctly.

TL;DR

Yes, Whirlpool as a plain hash is vulnerable to length extension attacks.
HMAC constructions prevent length extension attacks, which voids that problem.


Is it OK to use r-value from ECDSA signature (r, s) to prevent replay attack? ECDSA signatures are malleable. Given a valid signature (r, s), one can create a second valid signature by negating the s value.
I have searched workaround for this issue, and https://yondon.blog/2019/01/01/how-not-to-use-ecdsa says:

One solution to defend against signature malleability based attacks is to enforce a single canonical signature for a given public key and hash which is the approach taken by Bitcoin. More specifically, the Bitcoin core client software will only accept “low s-value” ECDSA signatures where a signature has a low s-value if s is less or equal to half the curve order [3]. The secp256k1 curve library used by the client will always generate signatures in low s-value form and the verifier expects provided signatures to also be in low s-value form [4].

Another solution is to avoid using signatures in identifiers or at the very least making sure to use unique values in the identifier creation process i.e. a nonce in the signed message. Unless there is a single canonical signature for a given public key and hash, signatures cannot be relied upon as unique identifiers.

What I wonder is, is it okay to use r-value instead of s-value for replay detection? One the first thought one should use s-value, because it is derived from a given message. r-value is not derived from a given message, but it uses k-value, which should be a random value. If duplicated k-values are used with same private key the key can be leaked, so signer have to generate distinct k-values. This makes me think r-value can be used to prevent replay attack.
Is there any problem if I use r-value to prevent replay attack?

I have to be honest and say that I never really understood why systems use the signature as the record rather than just the hash of the message that was signed. If that was used, then there would be no problem with using malleable signatures. If someone has a reason why not to just do what I said, please let me know and I'll change the answer.
More to the point of the question, there is no reason why not to just use the $r$ portion. If this repeats in two different valid signatures, then the signers can each learn the other party's private key. This is because by dividing the $s$ portions in the signatures, the $k^{-1}$ part falls away. Then, given one of the private keys it is easy to learn the other private key. As such, this should not be a concern to anyone (i.e., if it could happen then malleability is far from the problem).


Using GMAC for Authentication without encrypting the message I am pretty new to cryptography and have a sample of GCM mode of operation for AES.
PFB the code

    Cipher c = Cipher.getInstance ("AES/GCM/NoPadding");
    final int blockSize = 96;//c.getBlockSize();
    final byte[] ivData = new byte[blockSize];
    System.out.println("IV :- "+new String(ivData) );
    final SecureRandom rnd = SecureRandom.getInstance("SHA1PRNG");
    rnd.nextBytes(ivData);
    System.out.println("IV :- "+new String(ivData) );
    /**
     *
     */
    GCMParameterSpec params = new GCMParameterSpec(blockSize , ivData);
    SecureRandom sr = new SecureRandom();
    byte[] aesKey = MessageDigest.getInstance("MD5").digest(
            "som3C0o7p@s5".getBytes());
    byte[] ciphertext;
    byte[] head = "Header information".getBytes();
    byte[] data = "Data to encrypt".getBytes();
    sr.nextBytes(aesKey);
    SecretKeySpec sks = new SecretKeySpec(aesKey, "AES");
    c.init(Cipher.ENCRYPT_MODE, sks, params);
    c.updateAAD(head);
    ciphertext = c.doFinal(data);
    System.out.println("done   "+ new String(ciphertext));

    c.init(Cipher.DECRYPT_MODE, sks, params);
    c.updateAAD(head);

    ciphertext = c.doFinal(ciphertext);
    System.out.println("done   "+ new String(ciphertext));

But I need to do Authentication using GMAC. How do I do authentication using GMAC without encrypting/decrypting? Any pointers or suggestions will be very helpful.

GMAC is quite simply GCM mode where all data is supplied as AAD (or additional authenticated data), or as NIST SP 800-38D puts it:

  If the GCM input is restricted to data that is not to be encrypted, the resulting specialization of GCM, called GMAC, is simply an authentication mode on the input data.

If you don't have access to a cryptographic provider that supports GMAC directly (e.g. Bouncy Castle provides a AES-GMAC JCE Mac) you can simply use any AES/GCM implementation by providing all data as AAD, and an empty message for encryption.

e.g. adapting your example to do GMAC only:

... as for AES/GCM ...
c.updateAAD(head);
c.updateAAD(data);
byte[] mac = c.doFinal();
System.out.println("GMAC: " + SomeHexEncoder.encode(mac));

If you need to be certain you're getting it right, the GCM/GMAC test vectors from the NIST CAVP page can be used (everything with a PTlen = 0  is a GMAC test vector).


Using RSA signature as a secret material Can an RSA signature of a randomly generated seed be used as a secret material (for further protection of some data)?

That sounds like some sort of KDF - but here built on top of the RSA signature operation, instead of the encryption/decryption operation, that is typically used by KDFs. (Or are there some known KDFs that work that way?)

Such usage of signatures is unusual, as conceptually the signature is intended to be a non-secret information to be shared with other parties. But are there any known cryptographic concerns here, or maybe some cross-protocol pitfalls?

Note that the question assumes the PKCS#1 v1.5, as the PSS signature includes randomness and therefore can't be directly used for deriving a stable secret.

Yes, the idea of using RSA signature as KDF can work. The KDF's key will be the RSA private key, and the other input of the KDF will be the message to sign. Other requirements:

Either:

The signature is post-processed by a cryptographically secure PRF, e.g. a hash (which will make the output of the KDF indistinguishable from random, and the KDF uninvertible).
Perhaps: It is kept only suitably little low-order bits of the raw output of the integer constituting the RSA signature. Without proof, I conjecture that for $n$-bit RSA, and secure deterministic signature padding, the low-order $n/3$ bits are indistinguishable from random, and the KDF uninvertible (including with the public key).
It maters neither that the "secret material" output of the KDF is distinguishable from random, nor that the input of the KDF is reconstructible form its output (e.g. by one holding the public key, or because some bits are distinguishable from random).

It is used a secure deterministic RSA signature scheme, including RSASSA-PKCS1-v1_5 of PKCS#1, and ISO/IEC 9796-2 scheme 1 and 3.
The signing procedure does not force something variable in the signed message, nor in the part of the signature actually used.

Requirement 1 insures that the output of the KDF has the desired properties. With 1.1 or perhaps 1.2 (an unproven shortcut to save a hash), the output of the KDF is indistinguishable from random, and the KDF is not invertible. With 1.3 the signature itself can be the output (no matter how it is formatted, including e.g. base64), and that could be usable for a KDF generating, from public material, some output that only needs to be unpredictable and not colliding, but can be long and distinguishable from random.

Requirements 2/3 are there to insure that the KDF is worth the name function, that is the same input always yields the same output. Requirement 2 excludes randomized RSA signatures, including  RSASSA-PSS of PKCS#1v2, and ISO/IEC 9796-2 scheme 2. Requirement 3 excludes, for example, a Smart Card that would increment an internal counter at each signature, and force that in the message being signed, or (combined with 1.1 or 1.3) as a suffix to the signature.

Unfortunately, I know no reference.


Was Enigma really that hard to crack, given that you had access to hundreds of messages per network per day? Well, I guess that I have always been a little bit suspicious ... so to speak ... of the "official stories" about the difficulty of recovering Enigma message texts during WW2, because it seems to me that they're always focused on recovering "one message, in isolation."  Whereas, the actual situation faced by the intercept stations is that they were every day flooded with messages ... all of them encrypted using exactly the same (of course, unknown) network-key settings, differing only by their per-message keys.

So – my question is: "did all of that 'daily network-key mumbo-jumbo' actually matter," if you could be assured of a sufficient number of messages each day which ultimately differed from one another only by a three- or four-letter wheel setting?

I could go on at some length, but I think the question is clear:  could not cryptanalysts have exploited the process of statistically comparing the gathered messages against each other, treating most of the machine as simply "a pair-swapping transposition table that didn't change?"

Yes, it's just that the messages were often low value.

There was nothing like gps back then, you would not get a real time location of a submarine. At best you'd get a lat/long which is precise to several km and then spend hours trying to get a plane there.

You'd get vague obvious warnings like "Germans may be attacking this convoy"- and there was no central directions, it was up to the uboat commander to decide the details .

But that was important enough that the government gave them a few people to help them crack these messages.

So given such a small, resource poor team was allocated to the task it was a big accomplishment.


Diffie-Hellman algorithm and MITM attack How does the Diffie-Hellman algorithm prevent MITM attack?

I have tried to search about it but i couldn't find any understandable reasons.

The problem lies in the trust of the public key. If an attacker can simply replace one of the exchanged public keys with his own then an active MITM attack is possible. The attacker simply replaces both public keys with his own and proceeds to create two channels that rely on the shared secrets.  For ephemeral key pairs - as commonly used - the key pairs are short lived and the public key is not trusted so DH key agreement is then inherently insecure against MITM attacks.

This is the default for all TLS 1.3 cipher suites and all TLS 1.2 suites that start with DHE or ECDHE. These suites therefore have to rely on other methods of authentication to mitigate the MITM attacks.

So the common ephemeral-ephemeral Diffie-Hellman scheme does not protect against MITM attacks, and your premise is false.

Some DH protocols where both parties are authenticated may actually prevent MITM attacks. In static-static DH the public keys of both parties may be trusted and therefore the DH will provide entity authentication of both sides, rendering MITM impossible.

This is not a common method of operation at all. It seems TLS can offer static-static DH, but it seems a rare find. Because the key pairs are always identical the protocol relies on an additional nonce - applied during or after the key agreement - to make sure that the resulting shared secret changes on every execution of the DH key agreement protocol. The scheme where the nonce is applied during key agreement is not offered by many implementations.

If just one key pair is static and the public key is trusted then the party verifying the validity of the public key will see the invalid public key, and break off the handshake of the protocol used. Ephemeral-static DH is therefore also invulnerable against MITM attacks, even if just one party gets authenticated. Of course the party that accepts the ephemeral public key will still not have any idea who he's talking to. This is e.g. not a problem on internet sites as they don't care about who reads them - they offer additional password authentication where required.

Ephemeral-static key agreement is present in the TLS cipher suites starting with DH_ and ECDH_. This method of authentication is however not present in TLS 1.3 anymore. The authenticated DH protocol requires an DH-based certificate to be able to trust the public key. These kind of certificates are hard to come by. In practice only certificates that use RSA or ECDSA for authentication are used, rendering these suites useless.

Ephemeral means temporary, or fleeting. Ephemeral key pairs should be generated on each invocation of DH, and the private key should be destroyed to achieve so called forward secrecy. Some servers cheat - because key pair generation can be relatively CPU expensive - and reuse the key pairs for a longer time or even until the server is rebooted.


Bandwidth-efficient oblivious transfer Alice has two 1GB files, and Bob wants one without Alice knowing which. Can this be done with less than 2GB (1GB for each file) of bandwidth between Alice and Bob?

I wonder if it's possible to do it with indistinguishability obfuscation. Let's say that the two files have hashes H1 and H2, and that Bob knows those hashes. He can give Alice an obfuscated program that checks the two files against H1 and H2, aborts if the check fails, and if not returns one of the two files (say the one corresponding to H2) encrypted against his public key.

Alice can make sure that both files are not transferred by capping the response to 1 GB. Alternatively Alice can provide a zero-knowledge proof that the response of the obfuscated program is exactly one of the files.


Indistinguishability attack example I want solve the next exercise. The author defined the experiment for the cryptosystem $\Pi$, the adversary $A$ and the security parameter $n$ as follows

$\mathsf{PRIV_{EAV}}(\Pi,A,n)$

The adversary $A$ get the input $1^n$ and choose two messages $m^{(0)}$, $m^{(1)} \in M$ with same length;
One key $k \in K$ is generated using $\mathsf{Gen}(1^n)$, and one bit is chosen uniformly at random. Then the message $m^{(b)}$ is encrypted and sent to $A$;
Eventually $A$ outputs b';
If $b=b'$, the experiment result is 1. Otherwise 0.

Definition A cryptosystem $\Pi$ has indistiguishable ciphertexts in the presence of an eavesdropper if for all adversaries $A$ there exist a negligible function $\mathsf{negl}$ such that

$$\Pr[\mathsf{PRIV_{EAV}}(\Pi,A,n)=1]\leq 1/2 + \mathsf{negl}(n).$$

My question:
How will I be able to prove that the cryptosystem described below is not secure under the definition above.

Cryptosystem $\Pi$:

$\mathsf{Gen}(1^n)$ chooses a bitstring $k \in \{0,1\}^n$ uniformly at random,
$\mathsf{Enc}(m,k)$ works as follows: The message $m$ is split into blocks $m_0, m_1, \dots ,m_l$ of $n$ bits. Each block is encrypted separately, as $c_i = m_i \oplus k$. The ciphertext is then the concatenation of the encrypted blocks $c_0, c_1, \dots ,c_l$;
$\mathsf{Dec}(c,k)$ is analogous to Enc, but permuting $c$ and $m$.

Notation

$K$ is the key space, $M$ the message space and $C$ the ciphertex space

To prove that a scheme is not secure under such a definition you usually would propose an algorithm such that the experiment described in your question outputs $1$ with probability non-negligibly larger than $1/2$.
As this looks very much like a homework problem I will not give you a solution. However constructing the algorithm is actually very simple in this case. You only need to think about how you would choose the messages $m^{(0)},m^{(1)}$ in such a way that you would be able to distinguish their ciphertexts.
As a hint: The deterministic nature of the encryption-process could be a problem here, and you can actually distinguish with probability $1$.


Can you create asymmetrical encryption algorithm from symmetrical, without knowing how the algorithm works? Let's imagine that we have some symmetrical encryption algorithm, that has only two functions: Encrypt(Data, Key) and Decrypt(Data, Key). Let's say that the algorithm is strong and quick, but we don't know how it works. Is it possible only using those two functions to create a usable asymmetrical encryption algorithm? If not, is there any way to add anything that will help us create one?

It is not known whether it is possible to construct secure public-key encryption schemes from private-key ones (and by extension, from one-way functions). From Barak's recent survey:

  One could ask if there really is an inherent difference between public-key and private-key cryptography or maybe this is simply a reflection of our ignorance.  That is, is it is not possible to build a public-key cryptosystem out  of an arbitrary one-way function and hence base it on the same assumptions as private-key encryption? The answer is that we do not know

In fact, this is one of the most important open questions in cryptography, along with the question of whether one-way functions exist. So, in practice you can consider that it is not possible, and consult the above for a survey of the known methods to construct public-key cryptosystems.

See also Impagliazzo's "Five Worlds"; your question can be reworded as: is it possible that we live in Minicrypt, the world where one-way functions exist but public-key cryptography does not?


Decrypting DES - limited information I have a list of DES encrypted strings/data, they come in two lengths, 32 chars hex (16 bytes) or - I believe - 64 chars. I know the key, which is 8 ascii chars (I might add that I am the rightful owner of the key and all data). Is is possible to decrypt the strings, given this information, or is is impossible without additional info about the implementation, IV's, padding whatnot?

That should be possible yes. It's probably ECB or CBC mode encryption. If it is CBC mode encryption then the first 8 bytes (16 hex characters) may be the IV. Otherwise it is likely to be a vector consisting of 8 zero bytes (or eight 00 hex characters of course).

I presume here that you can distinguish the result from random of course. If that's not the case you'll have to guess the encryption mode & IV used to encrypt.

If you can only decrypt the later part of the ciphertext then you are using an incorrect IV.

In the worst case you also have to try CFB or OFB or even CTR, but that's relatively unlikely.

Note that you first have to decode the hexadecimals to bytes. The key is probably already the same as the ASCII characters when viewed as bytes.


Is TEA considered secure? Wikipedia claims that the best attack on the surprisingly simple TEA block cipher, that isn't a related-key attack, has a time complexity of $2^{121.5}$.

So despite how unsophisticated the cipher looks, if I use a KDF properly and don't use related keys, TEA is secure?

Yes, AFAIK the original TEA is safe and generally fine when

keys are random (key change should be atomic and with a fresh random key);
the 64-bit block size is not a concern (say, an operating mode other than ECB is used and the key is changed before a gigabyte worth of data);
the relative slowness is not a show-stopper;
side-channels are not an issue, or are taken care of (which is not especially hard; in particular TEA is inherently immune to timing attacks).

I'm not aware of any attack in a random key setup requiring much less work than $2^{126}$ encryptions (as required for brute force given known equivalent keys). The best result I know is Jiazhe Chen, Meiqin Wang and Bart Preneel's Impossible Differential Cryptanalysis of the Lightweight Block Ciphers TEA, XTEA and HIGHT (AfricaCrypt 2012) (alternate link to free, updated paper), which claims success against 17 rounds out of 64. This suggests there is some safety margin.

Vikram R. Andem's thesis (University of Chicago, 2003) also concluded TEA is safe, but the work is a bit outdated.

Answering the comment, reasons TEA is not much used:

TEA came much after DES, which was standard and pushed by authorities (initially, because DES could be broken if needed due to its purposely small key size).
3DES is adequate for many uses, and most importantly is standard.
TEA came significantly after IDEA, which was faster on most CPUs of the time.
The security claims made by David J. Wheeler and Roger M. Needham in TEA, a Tiny Encryption Algorithm (proceedings of FSE 1994) where non-committing ("It is hoped it is safe") and came only with very basic justification.
TEA was not defined in a manner suitable for interoperability: the mapping of octet strings to key and data has no standard definition (if I want TEA test vectors as octet strings endorsed by some official body, I do not know where to look! DES is much better in this regard). Even the number of rounds was not carved into stone: the article says "sixteen cycles may suffice and we suggest 32"; notice that this sentence recommends 64 rounds!
TEA quickly turned out to be vulnerable under related-key attacks. This is not a problem when the key is random, but does not inspire confidence (especially since that, and the trivial equivalent keys, was not considered in the original article).
XTEA was introduced shortly after TEA to fix related-keys attacks; XTEA did not meet its design goals, and needed a correction XXTEA; the later lost some of the simplicity of TEA, and requires slightly more rounds for equivalent security under random key when used as a 128-bit block cipher; also, XXTEA is badly broken in its wide-block variant (essentially because it uses too few rounds), see Elias Yarrkov's Cryptanalysis of XXTEA (2010).
Each TEA key has a trivial equivalent key; normally this is a non-issue (when keys are 8-octet strings, DES is much worse); but amazingly, one of the few notable uses of TEA (as a building block in a poorly designed hash used in the original XBOX) fell precisely because of that!
The above 4..8 tarnished the image of TEA (decision-maker often choose ciphers based on how they perceive its security or professionalism, or even on how they believe customers will perceive the choice!); 5 and 7 even created confusion about what TEA actually is (as illustrated by linking to the wrong algorithm in the initial question, and my mistake about the number of rounds in my initial answer).
In hardware, TEA would be high-latency (and thus slow in CBC, OFB, CFB modes), because of its many rounds; as a mater of fact (and perhaps consequence) there is no hardware for TEA when there is for DES, 3DES and AES, including for the later in many modern CPUs; that often makes TEA much slower than competitors.
Nowadays, 64-bit ciphers are passé.

Note: The most recent related-key attack on TEA that I know is by John Kelsey, Bruce Schneier, and David Wagner, Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA (ICICS 1997); it claims success with only $2^{23}$ chosen plaintexts and single related key query, but of a kind quite unrealistic: the related key swaps the halves of the original, plus other minute changes. However attacks only get better, and any key used for TEA really should be random.


Explanation of vector in Visual Cryptography I'm starting to study about visual cryptography, but I am stuck with the following problem.

On paper "Visual Cryptography" by Moni Naor and Adi Shamir, on page 6. How to read/what is the meaning of

$$J^0_i = 0^{i-1}10^{k-i}$$

and

$$J^0_k = 1^{k-1}0$$

where $1 \le i \le k$?

Can someone explain how to read it? Because I think I misunderstood.. And also I'm happy if anyone gives me a reference to learn it.

This is string notation: $J_i^0=0^{i-1}10^{k-i}$ means i-1 consecutive 0's followed by a 1 (we don't write $1^1$) which is then followed by k-i consecutive 0's. So $0^{3}10^{4}$ is $00010000$.

As for $S^t[i,x]=\langle J_i^t,x\rangle$, with $t\in \{0,1\}$ this is an inner product of $J_i^t$ with $x=(x_1,\ldots,x_k) \in \{0,1\}^k$ so in general $S^t[i,x]=x_i$ (only the 1 component in $J_i^0$ picks up a nontrivial value. Thus $S^0[2,x]=0\times x_1+1\times x_2+0\times x_3=x_2$ and $S^0[2,101]=0,$ while $S^0[2,010]=1.$ I agree it is quite cumbersome.

Generally, a good idea is to try to find "slides" as opposed to papers, where examples are usually given to make notations clear.


Entropy vs predictability in PRNGs If entropy is the measure of surprise, and a given PRNG has a uniform distribution, then the entropy would be high. So the Mersenne Twister(MT) has high entropy.

But the MT is also predictable. You can retrieve its past bits and predict its future bits.

What's the relationship between entropy and predictability?

entropy is the measure of surprise

That's informal, short and non-quantitative, but correct within that. In the case of a Random Number Generator, we must make that: entropy is the measure of surprise in the outputs of the RNG, for one skilled person (with arbitrarily large computing power) knowing the RNG design including any parameter (for MT: the Mersenne prime used, and a few others). That's for unknown seed (if any) assumed uniformly random but arbitrarily large computing power of the skilled person (unless otherwise stated).

The entropy considered here is a property of the generator, not that of one particular bitstring that it outputs.

Entropy further can be defined for the total output of a generator, or per output bit. In cryptography we measure the entropy in bit, so that it is 1 bit per output bit for an ideal uniform True RNG.

For any Pseudo RNG, the whole output is predictable from design, parameters and seed, hence the entropy in the whole output is limited to the entropy in what generates its seed, which is finite. And the entropy per output bit decreases to zero as the output size increase towards infinity.

  the Mersenne Twister(MT) has high entropy.

No, because it is a PRNG (see above).

  the MT is also predictable.

Yes, with enough output, and little computing power.

  What's the relationship between entropy and predictability?

If a bitstring generator has the property that it's full output is predictable from a finite length prefix (as is the case for MT), then this generator has finite total entropy (bounded by said finite length in bits for Shannon entropy in bits), and vanishingly small entropy per output bit.

The converse is false for practical definition of (un)predictable. In particular, there exist practical Cryptographically Secure PRNGs (thus of finite total entropy) that are practically unpredictable.

To make things quantitative: consider a generator $G$ of arbitrarily long bitstrings. Note $G_b$ that generator restricted to its first $b$ bits. $G_b$ is susceptible to generate $2^b$ different $b$-bit bitstrings $B$ with respective probability $p_B$ (possibly $0$ for some $B$), with $1=\sum p_B$ (the sum being over $2^b$ terms $B$). $G_b$ has Shannon entropy in bits
$$H(G_b)=\sum_{B\text{ with }p_B\ne0}p_B\,\log_2\left(\frac1{p_B}\right)$$
and its average entropy per bit is $H(G_b)/b$.

For an ideal TRNG (which output is uniformly random independent bits), and any $b$, all $b$-bit bitstrings are equiprobable with $p_B=2^{-b}$ and it comes $H(G_b)=b$.

For any PRNGs with $s$-bit seed (per any distribution), $H(G_b)\le \max(b,s)$. The entropy of the generator's whole output is $H(G)=\displaystyle\lim_{b\to\infty}H(G_b)$. That is maximal with $H(G)=s$ when all seeds generate different outputs and the seed is uniformly random.


What is the origin of the word "Keccak"? Where does the word or acronym Keccak come from?

Guido Bertoni, Joan Daemen, Michael Peeters, and Gilles Van Assche. Keccak sponge function family main document. Submission to NIST (updated), 2009.
"NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition". NIST 10/2/2012.

According to J.-P. Aumasson (who's one of the authors of another SHA-3 finalist, BLAKE, and who participated in the cryptanalysis of Keccak), the name "Keccak" is a variant spelling of "Kecak", a type of Balinese dance.

So far, that's the most authoritative reference I've been able to come up with.  It should be noted that naming crypto primitives after dances is hardly a new thing; see e.g. D. J. Bernstein's "latin dances" (Salsa, Rumba and ChaCha).


Asymmetric Encryption - How is the Public Key Being Shared? I've been reading up on the relationship between private keys and public keys (as well as hashing), and I watched a few videos, but I am still a bit confused.

I don't have a programming background, and I want to be able to explain these things to an "everyday person".

What I found is that before a message is "encrypted" with a "public key" that key FIRST must be shared with the receiver.

How is the public key being shared?

Thanks for your help.

The key is shared via email, via scp/rsync/ssh-copy-id (remote copy), or by editing the settings of your account on a website. If you look in a web application that supports PKI, there will be an option under settings where you can upload your public key. Running an agent on your trusted OS machine (which has your private key) allows automatic verification via custom client software. It will understand you have an agent, then verify your local private key against the server's known public key.

The metaphor used is that of an empty box. You give a friend a padlock, but you keep the key. They put valuables in the box, and close the padlock you gave them on the box.  Now only you can open the box and get the valuables. The public key is the padlock. The private key is the key. Imagine that anyone can have the same padlock all over the world, but only you can open whatever they send you.


How to prove the security of the PRNG? Are there any realties tests or criterias that prove the security of the PRNG?
What kind of tests or criteria?

We currently have no way to prove that a specific PRNG is cryptographically secure.  In fact, we currently cannot prove that there exists a cryptographically secure PRNG (!).

If you scale back the requirement from "mathematical proof" to "something we generally accept", there's still no way for an automated test to verify that a specific output is cryptographically secure.  Yes, it can run a series of statistical tests, and verify that, from that perspective, it looks like what we expect a random stream to be.  However, that is not sufficient; to be cryptographically secure, we require that someone cannot devise a clever test (using knowledge of how the PRNG works internally) that distinguishes it from random.  The hard word (for an automated test) is the word "clever"; automated tests have great difficulties with "cleverness".

Here's a little thought expirement that demonstrates one of the subtleties; suppose I generate a PRNG using AES in counter mode; that is, I pick an initial 128-bit value $N$ and an AES key $k$, and produce the sequence:

  $AES_k(N), AES_k(N+1), AES_k(N+2), AES_k(N+3), ...$

If I pick $k$ and $N$ randomly, and keep them secret (and keep the number of outputs within the above sequence to significantly below $2^{64}$), then this is, as far as we know, a cryptographically secure PRNG.

However, suppose I do the same, but instead of picking $k$ randomly, I use a fixed public value.  In that case, the sequence is known not to be a CSPRNG; it is easy to test (using two adjacent outputs), whether the output is from this specific PRNG.

Here's the point: publishing $k$ or keeping it secret does not actually change the output.  However, even though it doesn't, it does change whether we have a CSPRNG or not.

So, going back to your question: we do have things that we believe are CSPRNG (such as the above AES counter mode with a secret key); why do we believe those?  Well, that's because we have clever people (that is, people that have demonstrated skill in finding clever ways to break other CSPRNGs) analyze the PRNGs.  It's not an ideal solution (it's possible that there is a way to break it, and our clever people missed it); however it's better than any other way we have.


What is the most efficient attack on NTRU? So, I got how finding the private key is equivalent to resolving the SVP. I also understood that the LLL algorithm can only be used in small dimensions. Now, I wonder what is the most efficient attack one could do? Does it have to be comprehensive like the meet-in-the-middle one? Is it possible to use the LLL to speed up the process?

Thanks!

I am a cryptographic researcher at Security Innovation, which acquired NTRU Cryptosystems.

  Now, I wonder what is the most efficient attack one could do? Does it have to be comprehensive like the meet-in-the-middle one?

The most efficient attack (the terminology "best known attack" is often used here) is the hybrid attack of lattice reduction and meet-in-the-middle attack from Nick Howgrave-Graham at Crypto 07, available at:
http://link.springer.com/chapter/10.1007%2F978-3-540-74143-5_9

In this type of attacks, one performs partial lattice reduction on the NTRU lattices, and then uses a meet-in-the-middle search on the remaining part of the lattice. It combines the strength of both techniques.

For a given NTRU lattice, one need to fine-tune the parameters of the hybrid attack, so that the effort to do lattice reduction is the same as the effort to search. The latest analysis of this attack against NTRU cryptosystems can be found from: http://eprint.iacr.org/2015/708

  Is it possible to use the LLL to speed up the process?

Exactly. One can view the lattice reduction part as a pre-processing of a searching attack, which allows one to reduce the searching space.

PS: LLL algorithm is not strong enough for large dimensional NTRU lattice, even in the partially reduced scenario. One needs to use the BKZ/BKZ2.0 algorithms.


How do I properly calculate an inverse element for curve25519 when implementing Sphinx password store protocol? There's a new password store mechanism, called Sphinx
http://webee.technion.ac.il/~hugo/sphinx.pdf which is very nice and protects from device or user compromise. I haven't found any implementations and tried to do my own using curve25519 primitive and libsodium.

There's login phase when user and device do communication and that's where I got stuck, though it looks pretty simple.

I convert hash to a valid curve point x using elligator2.
Then scalar multiply it by some random ρ. Then "device" multiplies it by its k.

So, I have β = x * ρ * k.

I'm stuck at the point where I need to do β1/ρ

in Ref10 implementation of curve25519 there's "feInvert" function which I tried to apply to ρ and then scalar-multiply again, but that did not work.

While point coordinates lie in the finite field over which the curve is defined, in this case $GF(p)$ with $p=2^{255}-19$, the scalars that you use lie in a field defined by the order of the generator, which is different from $p$.

Therefore when you invert using feInvert you invert with respect to the wrong prime.

You need to invert in $GF(n)$ with $n=2^{252} + 27742317777372353535851937790883648493$.

Unfortunately for you, X25519 never use arithmetic in $GF(n)$ and the only operation required by ed25519 in $GF(n)$ is the modulo reduction, not the inversion.
Therefore there is no readily available code for that in the reference implementations, and you have to either look for some code that implemented it or build your own.


If OWF were to exist, do we know for sure that one of the candidate OWF would indeed be a OWF? We have several candidates for OWF, like multiplication/factoring and discrete exponencial/logarithm. What I am asking is:
Does the existence of one way functions imply that our candidate functions are indeed one way functions?
Is there a candidate one way function whose one wayness is directly tied to the existance of OWF?

Yes, you are looking for the notion of a universal one-way function.
Rafael Pass/abhi shelat's notes contain a construction on page 49. The construction is "unnatural" in the sense that it involves parsing the input to the OWF $y$ as a pair $\langle M\rangle || x$, where $\langle M\rangle$ is interpreted as the description of a Turing machine. Then you simulate $M(x)$'s executation for a bounded number of steps.
This is fairly typical of "universal" constructions (others exist, namely Levin's universal search). It is far from being feasible in practice though.
The notes mention that a "natural" universal OWF construction is a very open problem (circa 2008-ish).


Can i use Babai algorithm in q-ary lattice Let's assume we have the q-ary lattice

$$ \mathcal{L}_q({\bf A})=\{ {\bf z}\in \mathbb{Z}^{n} : \exists {\bf s}\in \mathbb{Z}^{n}_{q} \ , \ {\bf z}={\bf A s}^{T} \mod q   \},$$

where ${\bf A}\in \mathbb{Z}^{n\times n}_{q}$.

My question is, can I use the Babai's algorithm with input the matrix ${\bf A}$ and a target vector ${\bf t}\in \mathbb{Z}_{q}^{n}$,  to find a close lattice vector to ${\bf t}$ ?

No, you can't.

Babai's Nearest Plane Algorithm is supposed to receive a basis of the lattice, and $\mathbf{A}$ is not the basis of the modular lattice that it spans. If you give Babai's algorithm the matrix ${\bf A}$, it will work over the lattice $ \mathcal{L}({\bf A}) := \{ {\bf A}{\bf x} : {\bf x} \in \mathbb{Z}^n  \}$ instead of $\mathcal{L}_q({\bf A}) $. Therefore, it will probably output wrong answers.

For instance, if you take a vector $\mathbf{t} = (q, q, ..., q)$, then $\mathbf{t} \in \mathcal{L}_q({\bf A})$, therefore, Babai's algorithm must output $\mathbf{t}$ itself. But it is likely that $\mathbf{t} \not \in \mathcal{L}({\bf A})$, so, Babai's algorithm will output some vector different from ${\bf t}$.


Analog encryption algorithms I have a basic understanding of how strong encryption works on digital data. Bits can be changed so that they appear completely random and map one-to-one back to the original set, given the correct decryption key (and possibly other parameters).
But we always talk about digital encryption, never anything that would work on an analog system as far as I know. Good encryption didn't exist until relatively recently (or cryptanalysis would not have been as useful as it was during World War II) while phones and televisions, both using mostly analog signals until the internet came along, have existed for much longer. To my knowledge, nobody seems to have ever come up with secure and practical ways of encrypting them without converting them to a digital signal first.
Upon searching for analog encryption systems I came across DigiCipher (the successor to Videocipher), but it seems to use binary data since Wikipedia mentions that it uses a MPEG-2 compressed stream. Other sites mention that scramblers were used to prevent television channels from being watched by non-paying consumers, but scramblers have little to do with encryption since they (as the name suggests) are not intended to make the message unintelligible. Wikipedia's secure voice article only briefly mentions analog signals and then goes on to describe different digital systems.
The only real analog encryption scheme I found was on that Wikipedia page about secure voice communications. It works by adding noise before transmission and subtracting it on the receiving end. This sounds similar to a one-time pad, but it probably wasn't used only once, which means that all encryption became useless if the phonographic record(s) with the noise were stolen.
Thinking this through, digital encryption algorithms may be used to generate new analog records so that they're no longer a one-time pad. A secret key and variable number (e.g. yymmdd) could be used as input to a digital encryption algorithm, which then produces the noise to be added to the analog signal. Modern (secure) encryption algorithms are not doable by hand at a reasonable speed far as I know though, so I'm not sure how practical this idea is when all you have is mechanical or analog technology. They would have needed a computer.
Have we not (yet) figured out how to securely encrypt signals in a truly analog way (without the use of impractical one time pads), is it impossible (proven, somehow), or are existing algorithms just obscure because there are few applications for them (now that almost everything is digital)?

Some people define "encryption" in such a way as to exclude analog techniques -- there is no such thing as "analog encryption", they would say, because any analog method of obscuring the contents of a transmission is, by their definition, "scrambling", not encryption.

There have been several such scrambling ("analog encryption") techniques, including:

voice scrambling:

some early analog secure voice techniques, as you already mentioned, which added noise (or classic symphony music) from a phonograph at one end, and subtracted the "noise" from an identical, synchronized phonograph at the receiver.
Some analog voice scramblers do frequency inversion
Some analog "rolling code" voice scramblers frequently jump to a new frequency, hopefully faster than any eavesdropper can track, similar to frequency-hopping spread spectrum
Various combinations of the above -- for example, the analog A-3 and the 5B machine built to "decrypt" it which "the speech spectrum was being split into 5 bands, inverted and translated ... the cipher controlling the switching repeated cyclically after 36 sections."
I've heard rumors that some early speech scramblers used an analog vocoder to dissect voice (using a bunch of analog bandpass filters and an analog envelope detector for each one) into a few "control signals", each of which was transmitted on its own (very narrow) analog band (each one independently frequency-hopped, and random gibberish transmitted on unused bands?), and then the received control signals were used to reconstruct an approximation to the original voice.

Some analog "television scrambling" techniques:

Some scrambling systems transmit the visible part of each line exactly the same as normal analog video, but mangle the Horizontal Sync so that standard analog TV receivers can't lock on.
Some scrambling systems invert the black-white luminance of some lines, each line inverted/normal according to a bit from some pseudorandom number generator synchronized with the video signal.
Some scrambling systems invert the red-blue chroma of some lines, each line inverted/normal according to a bit from some pseudorandom number generator synchronized with the video signal.
Several scrambling systems use various combinations of the above.
Videocipher I, Leitch Viewguard, VideoCrypt-S, and Nagravision Syster all scramble video by sending the video scan lines in a scrambled order.
Telefirst ("Tele1st") apparently used some sort of analog scrambling technique (?)
Zenith Z-Tac cable scrambling system apparently used some sort of analog scrambling technique (?)
VideoCrypt I, VideoCrypt II, and Eurocrypt use line cut-and-rotate -- each line of the image is cut into 2 parts and swapped; the exact cutpoint is determined by a pseudo-random sequence generated by a smartcard from a seed value.

All of these systems were developed under severe cost constraints, so they sacrificed some security for lower cost to manufacture legitimate receivers.
So for a long time there was something like an arms race between the "defenders" (pay-per-view broadcasters, military radio manufacturers, etc.) and the "attackers" ( pirate decryption, military codebreakers and cryptanalysts, etc.).


Purpose of leading zero in PKCS1-v1_5 padding According to this document the padded message has the following structure:

$EM  \;= \; 0x00 \; || \; 0x02 \; || \; PS \; || \; 0x00 \; || \; M$

What is the purpose of this null byte at the beginning of the message?

After OS2IP decoding (also described in the document) to convert the message to a "bignum" I would expect this byte to be discarded, since a most significant byte of zero does not change the value of the number.

Also, when decoding the message, the standard document expects this zero byte to be present in the ouput too. Why should a bignum routine preserve a zero leading digit?

Instructions for decoding the message are given in the document and quoted below.

  If the first octet of EM does not have hexadecimal value 0x00, if the
  second octet of EM does not have hexadecimal value 0x02, if there is
  no octet with hexadecimal value 0x00 to separate PS from M, or if the
  length of PS is less than 8 octets, output "decryption error" and
  stop.

The first byte is 0x00, because some standards allow RSA key sizes $8b+1, b \in \Bbb Z_+$. Such key would have 0x01 at the first bit, but it is possible for almost all other bits to be zero. Thus, 0x00 as the first byte allows interoperability with all possible RSA key sizes.

NIST's recommendations and few other standards actually recommend only few specific key sizes, where usually the most significant bit is set so technically it would be possible to use shorter encoding.

The 0x02 is simply number describing what encoding and how RSA was used. Currently there are two commonly used choices: 0x01 (private-key operations [commonly signing]), 0x02 public key encryption. (In addition, 0x00 used to exists, but it is not in common use anymore.)

You may also take a look at http://tools.ietf.org/html/rfc2313 (PKCS#1v1.5) [especially section 8.1] for details, or one of later RFC's for PKCS#1v2.x.


Is there a way to break this encryption? I was wondering about making up a simple system to encrypt a file:

seed the random number generator with the passcode
generate as many random bits as the file has
xor

This has a vulnerability that if you encrypt two file A and B with the same passcode, xoring the two encrypted files would give the xor of A and B... so

seed the random number generator with the passcode concatenated with a hash of the file
generate as many random bits as the file has
xor

I think this fixes that vulnerability but a MITM could still flip certain bits inside the file by flipping bits on the encrypted file, so

seed the random number generator with the passcode concatenated with a hash of the file
randomly permute the plaintext in blocks of 128 bits
generate as many random bits as the file has
xor

I couldn't think of any vulnerability this system has. Do you know of any?

For the 3rd proposal, see my comment to the question for the issues/questions I have regarding there.

For the 2nd proposal, basically what you are proposing is using an IV with a stream cipher. The IV in this case being the hash of the file which would have to be shared in order to decrypt. In theory, it is a good idea. In practice, however, the track record is not very good. WEP used an IV with RC4, which led to a serious vulnerability. Furthermore, of the 34 stream ciphers submitted to eSTREAM, 10 were broken due to the way they used the IV during setup.

This shows that simply putting an IV and a password together is not necessarily better or even secure. You would need much stronger guarantees (for an example of a security proof for IVs in stream ciphers, see On the Security of IV Dependent Stream Ciphers).

So, to answer your question, in general, the construction is not secure. For specific stream ciphers, it might be possible to prove security.

One practical issue I see with this specific construction (even if a proper stream cipher is used), is that if I encrypt the same file with the same key twice, the ciphertext is the same. This leaks some information to an attacker, which is never a good thing.


Does a regularly reseeded PRNG provide backtracking resistance? I'm currently discussing a security topic with some of my classmates.

A cryptographic PRNG typically provides backtracking resistance if an adversary that compromises the internal PRNG state cannot distinguish previously generated values from random values.

Let's assume I use an invertible PRF as PRNG (e.g. AES in CTR mode with a true random key). Then this in general does not provide backtracking resistance since, after obtaining the internal state, I can calculate the previous output using the inverted PRF.

Now let's assume that I regularly reseed my PRNG, like for example every second. Does it then provide backtracking resistance or not?

We have now two opinions:

The PRNG does not provide backtracking resistance since it is possible to recover previous values within the compromised reseed interval.
The PRNG provides backtracking resistance since values beyond the reseed interval can only be guessed with negligible probability

Can someone explain who is right and why?

Best regards,
Matt

Here's a perhaps better way to frame it that won't lead to tedious semantic disputes:

Consider a PRNG with 256-bit seed $s$ that, on each request, produces $\operatorname{AES}_s(2) \mathbin\| \operatorname{AES}_s(3) \mathbin\| \cdots$ as output, and updates its seed by $s' = \operatorname{AES}_s(0) \mathbin\| \operatorname{AES}_s(1)$.  This PRNG erases its key after every request.
Consider a PRNG with 256-bit seed $s$ that, on each request, produces $\operatorname{AES}_s(0) \mathbin\| \operatorname{AES}_s(1) \mathbin\| \operatorname{AES}_s(2) \cdots$ as output.  If you schedule a timer event to reseed it every second, then this PRNG erases its key after every second.

Of course, in this case, you need some source from which to reseed it, so the story doesn't end here and is necessarily more complicated than the story in (1) for prompt key erasure.

The terms backtracking resistance and forward secrecy are not as helpful because they don't emphasize when the keys are erased.  Both PRNGs could be construed to provide backtracking resistance in some sense, but PRNG (1) is largely a better engineering choice than PRNG (2) because it doesn't need reseeding at all (so fewer things to wire up, fewer things that can go wrong) and it provides even prompter key erasure.

The question, as stated, is essentially about PRNG (2):

  We have now two opinions:

  The PRNG does not provide backtracking resistance since it is possible to recover previous values within the compromised reseed interval.
  The PRNG provides backtracking resistance since values beyond the reseed interval can only be guessed with negligible probability

  Can someone explain who is right and why?

You're both right: it provides backtracking resistance every second, but not every request, so there is a window of time in which state compromise could reveal future outputs, but it's small.  It's arguable, not a priori clear, which of these ‘backtracking resistance’ means, which is why I recommend emphasizing when keys are erased.


RSA Without Padding? I've been looking at the weakness with plain/textbook RSA, where the same message is encrypted and sent to multiple destinations. In this case, it is possible to recover the message.

Given that an attacker then knows the values of $m$, $c$, $e$ and $n$ in the following equation, is there any extensions which allows them to recover $d$?

$c = m^e \mod n$

No, an attack against RSA without padding that let one recover messages does not, as far as we know, degenerate into leaking a working private exponent $d$, or factoring $n$. In fact, even unlimited access to a decryption oracle performing $c\mapsto m=c^d\bmod n$ for any $c$ will not allow that either.

To back up the above, see this survey by Dan Boneh where it is Open Problem 1.


How Can I Know the Number of Points on an elliptic curve? If I have the following Elliptic Curve:
$$E: y^2 ≡ x^3 + 2x + 2   \mod 17$$

How Can I calculate the Number of Points on this elliptic curve $\#E$ ?

and how can I invest the following law which calculates the Number of Points on an Elliptic curve NPE:

$$NPE=1+p+\sum_{x=1}^{p-1} \frac{f(x)}{p}$$

As the astute commenters pointed out, small cases can be done by hand, while Schoof's algorithm can be used for large fields.

By the way, there is the well known bound
$$
q+1-2\sqrt{q}  \leq \#E \leq q+1+2\sqrt{q}
$$
on what you call NPE, due to Hasse-Weil, for curves over $\mathbb{F}_q.$ If $q$ is prime, the inequality is strict.


Given a list of ciphertexts, how to identify the ones that used the same key for encryption I'll start off by saying I am not looking for solutions here, just suggestions on how to proceed. I am given a short list of ciphertexts (20something) and I know that one of the ciphertexts has been encrypted with the same key.

I know that once I identify the ciphertext, I will do a crib drag attack, but my issue is with finding the ciphertext in the first place. Are there any suggestions as to how to approach this issue? All similar questions I could find online dealt with a list of ciphertexts that were all encrypted with the same key, which is much simpler to tackle.

The only thing I know about the plaintexts is that they are all in English. I could do all the possible XOR combinations and crib drag every single one of them but that seems terribly inefficient and not the correct way to go about it. Any suggestions are appreciated.

Update:
Unless I've misunderstood what Meir Maor meant (I couldn't find anything on "char level histogram"). I don't see how a frequency chart would help in this case, considering that only the key is the same between the 2 messages in a list of over 20.

If you assume the keys are random yet the plain text are english. Xoring two cipher texts with different keys will look like random noise. Yet if you xor two messages with same key you get a complex distribution of pairs of English messages, very not random. A simple histogram should be sufficient to tell the distributions apart.
If the keys are not random(possibly leading to other attacks) you will probably still be able to pull off the same attack though you will need to study the histogram of xoring English messages so you can detect it. With random keys it won't even be necessary.


Any ideas to make an Electronic Voter Machine more secure? EVMs are not secure they say. So how can we make it more secure tham the existing one using cryptography?

We can't make satisfactory Electronic Voting Machines. Their design face conflicting goals that are impossible to reconcile, even in the simplest conceivable use case: a yes/no vote, a single machine.

Count votes (or at least: determine if there was more yes than no) with the result public.
Limit voting to one per registered voter.
Keep individual votes secret, even from organizers or/and if a person casting vote is actively trying to prove how s/he voted (that requirement helps freedom of vote despite attempted bribery/duress), within the limits inherent to what gets published of the result.
Resist denial of service.
Convince reasonable observers with ordinary skills that the above goals are met, even if observers do not trust the organizers and designers of the machine, understandably so [*].

Among the few non-electronic approaches that work is one that evolved over time: paper ballot freely available to all, put in opaque envelope mandatorily in a private booth, with the envelope publicly inserted in a transparent urn (with mechanical interlock preventing unauthorized insertion), check of the voter's identity and that the voting role is unsigned right before that insertion, and signing the voting role right afterwards, with the urn and envelopes publicly opened in the end and counted, under public scrutiny all along.

Alternatives have been tried:

Mechanical counters, with interlocks preventing multiple voting. There have been jams (perhaps intentional). Only people understanding mechanical machinery (similar to watchmaking) can observe and confirm that counting work as intended before and after voting. And it is to fear that various side channels (lifting a cover hidding the value, sound, ...) can compromise vote secrecy. On the positive side, it can be me made slow and noisy to covertly alter the counters.
Electromechanical counters: reportedly more reliable, but side channels are rather worse, altering the counters might be faster and easier, and (because wires and air gaps can be hair-thin) an observer (needing basic understanding of electric circuit) could miss something redirecting counting to the wrong counter. While it would be conceivable and useful to make counters that the voter (only) can see moving when casting vote, without being able to tell the count, I have not heard that it was used.

The more we go towards modern electronics and complex cryptography, the worse the "convince reasonable observers with ordinary skills" goal is met. Finding backdoors in silicon and software is extremely hard, and entirely impossible at the voting location. For most reasonable observers, a finite field is a bounded piece of land.

[*] Voting machines in use in (few and mid-sized) French cities are purchased, stored, serviced and operated (with supervision from the ministry of home affairs) under the authority of the Mayor, yet are used to (re-)elect the Mayor. Their specification and type approval is under the authority of the ministry of home affairs, which head is chosen by the prime minister, which is chosen by the Président de la République, which the machines contribute to (re-)elect. In 2007 that election was won by the former head of the ministry of home affairs that gave delegation for establishing the specifications as law, and was again head of that ministry weeks before his own election and days before a software change was made to the most common type of machines. BTW that software is secret, and it's integrity is publicly demonstrated by a checksum that the software computes and displays. Descartes reportedly turned in his grave.


Applying Trapdoor Function directly to plaintext Suppose we have a secure trapdoor function defined on (G, F, F^-1) where G is a randomized algorithm outputs a key pair (pk, sk). Why would this trapdoor function become insecure if we apply F directly to plaintext message?
E(pk,m) = c = F(pk, m)

An eavesdropper could easily test any candidate message to determine

whether or that candidate message was the plaintext message.

def test_candidate_message_(pk,c,candidate):
 if c == F(pk,candidate):
  return True
 else:
  return False


DROWN - decrypting ServerVerify message is not enough? I have read this article, but I can't understand why after decrypting ServerVerify, the client needs to send the export grade PMS again...

  When exploiting these flaws the attacker will send its candidate
  cipher-text to the server and receive the “ServerVerify” message. The
  attacker will then perform a brute-force search over all 2^40
  possibilities for the export-grade PMS to find the PMS that derives a
  server session key that successfully decrypts the “ServerVerify”
  message. The attacker will know when a brute-force attempt is
  successful because the message will then decrypt into the random
  number he has previously chosen.

  Having found the PMS of the first message the attacker then submits
  the same candidate cipher-text again and receives the “ServerVerify”
  message. He now uses the PMS found from the first message to derive
  the server session key for this second session. If this server session
  key successfully decrypts the “ServerVerify” message then the attacker
  knows that the server has arrived at the same PMS twice, turning the
  server into a Bleichenbacher oracle.

If the ServerVerify is decrypted successfully, the attacker will get the random number generated at the begining of the handshake. Is it not enough to confirm that the derived session key he has generated with his PMS is the correct one?

I already know that if after re-sending the same packet, the decrypted ServerVerify is the same, so the session key is the good one (acting like an oracle). But I don't think we need to do this step...

Is it a mistake?

No, it's not a mistake. After Bleichenbacher's attack was discovered, the fix throughout SSL/TLS was to prevent the "padding oracle" by decrypting and following this strategy: if the PKCS#1v1.5 padding is correct, then use the PMS obtained; if the PKCS#1v1.5 padding is incorrect, then use a random PMS. This prevents the oracle since an attacker who doesn't know the PMS cannot distinguish these two events (they are also supposed to take the same amount of time). However, in SSLv2, since it takes only $2^{40}$ to brute force the server reply, it's possible to re-establish the oracle. Specifically, the attacker gives the ciphertext twice to the server. If the padding is correct, then the server will reply with the same key both times. If the padding is incorrect, then since the server chooses a random key in this case, it will reply with different keys. This enables the attacker to know if the padding in the RSA encryption was correct or not.


Difference between AES CMAC and AES HMAC? Can someone elaborate on how 'signing' is done using AES- CMAC and AES-HMAC?

HMAC Signing as I understand: Compute the HMAC( Hash the key and the input concatenated in a special way) Verification: Verify if for the given input and secret key the calculated HMAC(signature) is the same as that is computed. But how is AES used in conjunction with this? is it HMAC(AES(Data)) then what is CMAC?

CMAC signing as I understand: is to encrypt the input using the key by applying AES algorithm and then calculating  a MAC by applying a special concatenation step of the key and resulting encrypted data??. For verification, the signature should be compared with the newly computed CMAC of input and key at the receiving end.

Please clarify

Thanks.

Also, does openSSL libs support AES CMAC and AES HMAC?

A similar question as been asked before: Use cases for CMAC vs. HMAC?

To resume it, AES-CMAC is a MAC function. It can be seen as a special case of One-Key CBC MAC1 (OMAC1) which also a MAC function that relies on a block cipher (so AES in the present case).

HMAC is also a MAC function but which relies on a hash function (SHA256 for HMAC-SHA256 for example).

So the term AES-HMAC isn't really appropriate. If you read it somewhere, it could signify the process of computing a HMAC on the message you want to encrypt to ensure the integrity property (AES$[message ||$ HMAC$(message)]$ for example).

Note that there exists authenticated ciphers that simultaneously ensure confidentiality, integrity and authenticity.

  Also, does openSSL libs support AES CMAC and AES HMAC?

OpenSSL supports HMAC primitive and also the AES-CMAC one (see How to calculate AES CMAC using OpenSSL?)


How can I encrypt a plain text of length l to a ciphertext of a different length I'm trying to encrypt a plain text (of length l) and output a ciphertext of length t, where t does not equal to l.
How do i get a ciphertext that is shorter than the plaintext input?
How about if I want a ciphertext that is longer than the plaintext?

Also, assume if I already have a encryption function E, such that E takes l bit plain text as input, and outputs a l bit ciphertext. How can I use E to create a new encryption G, such that G solves the above problem?

It is impossible to have a ciphertext shorter than the plaintext, while still being able to decrypt it. This is quite obvious: an $\ell$-bit ciphertext contains at most $\ell$-bit of information, so as long as the messages have more than $\ell$ bits of entropy, some information is lost (and if it is longer than $\ell$ bit but has very little entropy, then you can compress the message before sending it).

In the case of public key encryption, in fact, if your message is $\ell$ bit long, you cannot even have a ciphertext of length $\ell$ if you want some important security properties: encryptions schemes are usually required to satisfy semantic security, which states that if a ciphertext encrypts one of two messages, it is infeasible to determine which one it encrypts (even knowing the plaintexts). But this implies that many ciphertexts must correspond to a same plaintext: if a plaintext is associated to a single ciphertext, one can break this property just by encrypting the two messages and checking equality with the ciphertext. Therefore, to get a probability, say, at most $1/2^{80}$ for the encryption scheme to be broken, a ciphertext will be at least 80 bits longer than the maximum size of a plaintext.

If you want a longer ciphertext, just pad with zeroes. You can make the ciphertext as long as you want that way.


OpenSSL: Call X509_verify_cert on a certificate with OIDs unknown to openssl I have a DS and a csca certificate that contain special OIDs from the BSI.
They are:

0.4.0.127.0.7.4.1.1 ECDSA with SHA1 (BSI)
0.4.0.127.0.7.4.1.2 ECDSA with SHA224 (BSI)
0.4.0.127.0.7.4.1.3 ECDSA with SHA256 (BSI)
0.4.0.127.0.7.4.1.4 ECDSA with SHA384 (BSI)
0.4.0.127.0.7.4.1.5 ECDSA with SHA512 (BSI)

openssl does not seem to know them so when calling X509_verify_cert() I get this error:

stdin: C = DE, O = MyFooBar, OU = Document Signer, CN = foobar ds
error 7 at 0 depth lookup:certificate signature failure
28308:error:0D0C50C7:asn1 encoding routines:ASN1_item_verify:unknown signature algorithm:.\crypto\asn1\a_verify.c:159:

I am not a crypto nor an openssl expert, but I know that there are other OIDs for "ECDS with SHAxy" that are known to openssl.
Would it be possible to just replace the OIDs in the certificate so that openssl applies the correct algorithms? Or this there a way to "configure" openssl and make it "learn" new OIDs?
Thanks!

Would it be possible to just replace the OIDs in the certificate so
  that openssl applies the correct algorithms?

No, this would alter the certificate and thus invalidate its signature, meaning you'd get a certificate error anyways with strategy.

However, I have searched around and by the looks of it, it's a "custom" version of the normal BSI issued ECDSA identifiers.

Normally, the OID-parent issued for plain ECDSA (BSI PDF) is 0.4.0.127.0.7.1.1.4.1, which makes sense because it is sorted under "algorithms -> id-ecc -> signatures -> 1 (ECDSA-plain)" under the BSI root node. Also note how this website says that 0.4.0.127.0.7.4 is unassigned, which means somebody could indeed have just used it "as a shortcut" to the desired signature algorithms.

Now there is one authoritative other mention, somewhere in the Doc 9303 series issued by ICAO for machine-readable travel documents, however I was not able to find this definition (and indeed there were no OIDs in the document where they allegdly were and the author making this reference left no contact info in his paper).

TL;DR: Chances are that this means that plain ECDSA with SHA-X was used and so I think standard ECDSA verification is worth at least a try.


How blockchain system manages it's memory limit for nodes? As we know, in the blockchain system every node has historical data that contains all previous transactions to maintain the integrity and approve the future transaction. What if blockchain is implemented in everyday life and people makes billions of transaction in a day, then a node must run out of memory sooner or later. How this is maintained or designed?

Right, most cryptocurrencies store all transaction data in the blockchain, which must be available to every node. You're right that this is a big problem for scalability.

There are several different kinds of strategies being developed to further improve cryptocurrency scaling. These strategies generally either involve sharding the blockchain into multiple related blockchains, so each node only needs to have some subset of the full blockchain (see Ethereum's Sharding FAQ), or moving transactions off-chain (Bitcoin's Lightning Network, state channels, Ethereum's Raiden, etc). Off-chain transaction systems build off of the idea that if two people are sending money back and forth between themselves, they can architect some smart contracts so they can send the transactions privately and instantly between themselves off-chain, and make an on-chain transaction containing all of the private transactions to safely reclaim their money if either defect, and a network can be formed between pairs of users like this to allow instant off-chain transactions between any two people in the network.


Is There an Opensource Manual Calculation of AES-128 bit? Is There an Opensource Manual Calculation of AES-128 bit as in Cronos

I have to learn calculations manually.

Project Nayuki has an Excel sheet in binary, XML and OpenDocument format. The code doesn't include any  Vusial Basic or Macros, they used only the spreadsheet's math functions; VLOOKUP, BITXOR, DEC2HEX, and HEX2DEC.

They have also, a nice video for AES on Youtube and a flash animation if you can run somewhere.


Property of negligible functions Suppose that $\mu(n)$ is a negligible function, which means that for every $c>0$ there is some $N$ such that for all $n>N$ it holds that $\mu(n)\leq n^{-c}$.

Now, imagine that some encryption scheme, signature scheme, or some cryptographic primitive in general has an "error" (distinguishing error, forging error, etc.) of $\mu(n)$.
Imagine that now I want to set up my primitive so that this error is no larger than $2^{-80}$.
If I had the explicit expression for $\mu(n)$ (which is likely to be the case if I read the security proof of the given primitive) then I would solve the inequality $\mu(n)\leq 2^{-80}$ for $n$.
In practice (even though this is not necessarily the case), negligible functions look pretty much like exponentials $2^{-n}$, so we know that this $n$ will be polynomial in $80$ and therefore it won't be too large.

Now think of the general case.
Suppose I want to find some $n$ such that $\mu(n)\leq 2^{-\kappa}$ for some $\kappa$, let's denote the minimum of such $n$'s by $n(\kappa)$.
We know that such value must exist simply because $\mu$ tends to zero as $n$ approaches infinity.
Moreover, since $\mu$ is negligible, intuition on the definition says that $n(\kappa)$ shouldn't be too large in terms of $\kappa$ (e.g. if $\mu(n) = 2^{-n}$ then $n(\kappa) = \kappa$).
My question is: how do we actually prove this?

Here's my question, extracted from the motivation above:

  Let $\mu$ be a negligible function, and let $n(\kappa)$ be the smallest $n$ such that $\mu(n)\leq 2^{-\kappa}$.
  Prove that $n(\kappa)$ does not grow too fast as $\kappa\to\infty$.

Part of the question requires to specify precisely what is meant by "too fast".
I would love some statement like "$n(\kappa)$ is polynomial in $\kappa$", but I'm not sure how to prove this.

I believe this property is important as this is one of the reasons why we choose negligible functions (besides being closed on additions and multiplication by polynomials): it allows us to get small error probabilities without increasing the security parameter too much.

Any insights on this are welcome.

The function $n^{-\log(n)}=2^{-\log(n)^2}$ is negligible, but $n(\kappa)$ for it is $2^{\sqrt{\kappa}}$ which is not polynomial in $\kappa$.

If we look at the functions $\mu_c(n)=n^c$, their $n_c(\kappa)$ is $2^\frac{\kappa}{c}$, so if $\mu$ is negligible, its $n(\kappa)$ must be smaller than those (at least for big enough $\kappa$, this is ok since you asked for the asymptotics). This means that $n(\kappa)$ is subexponential, i.e., $n(\kappa)=2^{o(\kappa)}$.


Algorithm for n-of-m keys with partial results Is there any known and proven algorithm which allows n-of-m keys en/decryption, but doesn't require the keys to be in one location? That is, it allows the plaintext (or ciphertext) to be encrypted (or decrypted) with one part of the secret, then passed on to another party, until n parties processed it.

Practically I'm looking for a solution to secret sharing where nobody is trusted to hold the complete key - even temporarily. It sounds like an area of homomorphic encryption, but I couldn't find any obvious software / papers.

Edit:
The scenario here is:
3 parties: plaintext generator, storage service, extractor.

The only allowed operations are:

generator stores an encrypted message, can encrypt together with storage service
extractor and storage service together (agreed by offline action) decrypt all messages stored by generator (at this time all messages can be deleted) - extractor learns the plaintext, but storage service must not

Explicitly forbidden scenarios:

storage service or extractor decrypting, or encrypting messages individually
storage service cannot learn the plaintext when generator is storing then

The way I see it, you have a few options. The right one will depend on the details of the application, which are sparse in the question.

Use a stream cipher (or stream-like mode). Each party has a separate key and encrypts/decrypts with their individual key. With this you only get n-out-of-n, not m-out-of-n where $m<n$.
Use MPC. You can evaluate the AES encryption/decryption circuit via MPC. It is fairly fast based on the numbers I've seen recently. Unfortunately, I don't think there is any good publicly released software out there to do this. Under this paradigm, each party would hold a share of the secret key and they would cooperatively work to do the encryption/decryption. The work I cited requires all n parties, but if the secret were originally shared with an m-out-of-n sharing scheme (like Shamir), you could convert that to an additive sharing (see this paper for a method of doing the conversion).

Some things to think about:

Who generates the key initially?
Who is suppose to receive the output of the operations?


What is more efficient, pairing based cryptography or non pairing based cryptography? As far as I know non pairing pairing based cryptography is less time consuming than pairing based because, pairing based uses complex operations. Are there any advantages of pairing based cryptography over elliptic curves without using pairing based cryptography?

If you can express your operation well using plain groups, go with normal elliptic curves. But the pairing adds additional mathematical structure, which enables new algorithms.

Some examples:

BLS signatures

They're verifiably deterministic and small, 2x security level, instead of 3 to 4 times, with DSA/Schnorr/ElGamal signatures.

These  use the pairing as a decisional Diffie-Hellman oracle.
Identity based encryption using the Boneh–Franklin scheme.


IKEv2 mutual authentication step I read from here that,
https://tools.ietf.org/html/rfc7296
it mentioned,
2.15.  Authentication of the IKE SA
the initiator
signs the first message (IKE_SA_INIT request), starting with the
first octet of the first SPI in the header and ending with the last
octet of the last payload.  Appended to this (for purposes of
computing the signature) are the responder's nonce Nr, and the value
prf(SK_pi, IDi').  It is critical to the security of the exchange
that each side sign the other side's nonce.
from part one(IKE_SA_INIT request), we have Ni, then we append Nr,
why we need to append the third part: prf(SK_pi, IDi') and then sign the msg?
why just signing Ni and Nr is not enough?

why just signing Ni and Nr is not enough?

Because we want to make sure that man-in-the-middle can modify (or hijack) the initial messages without being detected.
Consider this attack:

Alice sends an IKE_SA_INIT request to Bob

Mallet intercepts that message; he forwards his own IKE_SA_INIT message to Bob, using Alice's Ni value, but his own KE payload

Bob replies with an IKE_SA_RESP message, which his Nr value.

Mallet intercepts that message; he forwards his own IKE_SA_RESP message to Alice, using Bob's Nr value, but his own KE payload

Essentially, Mallet is establishing two separate IKE connections, one with Alice and one with Bob.
Alice then authenticates herself; if she just signed the Ni, Nr values she saw, Mallet could just resend that signature to Bob (which saw the exact same Ni, Nr) values, and so Bob would assume he's talking to Alice.
By appending the prf(SK_pi, IDi') value, this is not possible (because Alice and Bob don't have the same SK_pi value)


Additional Data in AEAD (Chacha20-poly1305 libsodium) I have recently been playing with Chacha20-Poly1305 in libsodium, and all of the examples state the additional data portion of the tag is stored in plaintext when encrypted. But from what I can tell the AD tag never actually gets put anywhere in the ciphertext. So if I were to simply transfer the ciphertext I would never actually be able to extract the AD portion (which is where I would like to store the nonce). And even if I were to just append the AD portion to the ciphertext afterward I am not certain the best way to retrieve it without doing something like OpenSSL with its Salted__ magic constant.
All of the examples say something like this:
#define MESSAGE (const unsigned char *) "test"
#define MESSAGE_LEN 4
#define ADDITIONAL_DATA (const unsigned char *) "123456"
#define ADDITIONAL_DATA_LEN 6

unsigned char nonce[crypto_aead_chacha20poly1305_NPUBBYTES];
unsigned char key[crypto_aead_chacha20poly1305_KEYBYTES];
unsigned char ciphertext[MESSAGE_LEN + crypto_aead_chacha20poly1305_ABYTES];
unsigned long long ciphertext_len;

randombytes_buf(key, sizeof key);
randombytes_buf(nonce, sizeof nonce);

crypto_aead_chacha20poly1305_encrypt(ciphertext, &ciphertext_len,
                                     MESSAGE, MESSAGE_LEN,
                                     ADDITIONAL_DATA, ADDITIONAL_DATA_LEN,
                                     NULL, nonce, key);

unsigned char decrypted[MESSAGE_LEN];
unsigned long long decrypted_len;
if (crypto_aead_chacha20poly1305_decrypt(decrypted, &decrypted_len,
                                         NULL,
                                         ciphertext, ciphertext_len,
                                         ADDITIONAL_DATA,
                                         ADDITIONAL_DATA_LEN,
                                         nonce, key) != 0) {
    /* message forged! */
}

But in real life you obviously only retrieve the ciphertext and would not have ADDITIONAL_DATA without extracting it. So what is the "standard" way of handling additional data in a AEAD scheme?
EDIT: Got the OpenSSL magic constant wrong.

First of all the Additional Data (AD) is not a tag. It is data that is also authenticated by the authentication tag. This authentication tag is appended to the ciphertext by libsodium. The tag doesn't consist of separate portions for AD and the ciphertext (and IV), the AD is taken into account during calculation of the tag.

The AD can be any data, including data that can be generated or data that is known in advance. In that sense it does not have to be send. How it is handled or generated is out of scope for the definition of the authenticated cipher. You do need all the AD data on both sides or you won't be able to calculate the authentication tag. The AD cannot be extracted from the ciphertext nor from the tag.

To my knowledge all authenticated ciphers already include the IV in the tag calculation, so there is no need to treat the IV as AD. It's actually a requirement for the CEASAR competition, so no doubt this algorithm will comply with that. Don't confuse or mix nonce and AD, they are different inputs to the cipher.

If you want a standard way of handling nonce, AD etc. you should look for a suitable container format such as CMS.


Security based on PRF I've seen that there is several kinds of PRF, and sometimes people speak about strong PRFs.

When proofs of a protocol or algorithm are given based on the assumption of the use of a PRF, are they speak implicitly about strong PRFs?

I disagree with the @RickyDemer.  The concept of a strong PRF has specific technical meaning and is distinct from a PRF.  This can be verified, say, in the Katz-Lindell textbook or by searching for the terms and looking at the lecture notes and papers that turn up.  An important case where this distinction comes up is with 3-round versus 4-round Feistel networks.  It is also a common exercise to build a PRF that is not a strong PRF.

There is a little variation on usage, as some theoretical crypto papers will only say "PRF" when they mean "strong PRF", but the vast majority distinguish between the terms.


Practical OWP of the set of $k$-bit bitstrings for low $k$ Down to what $k$ and how can we devise a practical, public, efficiently computable One Way Permutation $P$ of the set $\{0,1\}^k$ of $k$-bit bitstrings, if possible without involving a trusted party for parameter setup ? Note: I want $P$ to be a permutation in the mathematical sense, and computationally hard to invert for some definition of that.

For values of $k$ starting at bout $2000$, we can use the assumed hardness of the Discrete Logarithm Problem (RSA also works if we trust a party to generate and publish an appropriate public key, and destroy any clue that could lead to factorization of the modulus).

For example, with the DLP, we find the smallest prime $p$ at least $\sqrt[3]{9}\,2^k$ such that $q=(p-1)/2$ is also prime, find the smallest $g$ at least $p/\pi$ such that $g^q\bmod p=1$, and define function $F$ over the set $\{1,2\dots q\}$ as $F(x)=\min\big(g^x\bmod p,p-(g^x\bmod p)\big)$. As far as we know, $F$ is an OWP over that set. We then use cycling to reduce $F$ to a permutation $P$ of $\{0,1\}^k$: we convert the input bitsring to integer, add one, apply $F$ and iterate (on average $\sqrt[3]{9}/2\approx1.04$ times) until the result is at most $2^k$, subtract one, convert back to bitstring.

Addition: I'll cowardly let the answer state its security claim. Informally, I'd be happy with a vague argument that more than $\min(2^n,2^{128})$ cycles of classical CPU are required for anything that should require more than $2^n$ evaluations in the forward direction, like finding a bitstring $x$ with the first $n$ bits of $P(x)$ all-zero (or other arbitrary $n$-bit value defined independently of the definition of $P$).

Motivation: I read that OWPs are more useful than OWFs. I wonder if that matters in practice. I reason that if we can't get $k$ down to say 256, we could as well use as a practical equivalent of a OWP a hash of $k$ bit (and same input size); it's most likely not a OWP, but it can't be computationally distinguished from that if the hash is secure.

Here is an outline of a system that would yield $k \approx 256$.

Let us select an elliptic curve (based on a prime field of size $N \approx 2^{256}$ with:

Is secure, and has twist security (that is, the discrete log problem on the curve and on its twist is infeasible)
Has a single point of order two (the $x=y=0$ point)
Both the curve, and its twist form a cyclic group (which is mostly a consequence of the previous two assumptions)

We'll select a generator of the curve $G$ and a generator of the twist $G^*$ (note: if you are basing this on Curve25519, then the conventional $g=9$ does not work, as that generates a prime-order subgroup, not the entire curve)

Then, if the order of the curve is $q$ and the order of the twist is $q^*$, then every value between 1 and $N-1$ can be represented as either (but not both):

The $x$ coordinate of a point $kG$, for some $1 \le k < q/2$
The $x$ coordinate of a twisted point $kG^*$, for some $1 \le k < q^*/2$

So, if we map the integers $k \in [1, q/2)$ to the $x$ coordinate of $kG$, and the integers $k \in [q/2, q/2 + q^*/2)$ to the $x$ coordinate of $(k - q/2 + 1)G^*$, I believe that gives a hard-to-invert permutation of the integers in the range $[1, N-1]$.  And, you can use the tricks you have listed to make that down into a slightly smaller range $[0, 2^k)$.

Do you see any obvious problems with this?