texts: Generating interactive, secure multiple ECC key pairs deterministically

texts:
In Elliptic Curve Cryptography (ECC) assuming user A has a private public key pair of $S$, $P$ accordingly with generator point $G$ which as we know is: $$P=S*G$$
Assuming that user A wants to generate multiple key pairs deterministically to manage them easier and there is a user B who should be involved in the process to reduce single point of failure. Each time user A wants to generate a new key pair he needs to ask user B to provide him some secret so that user A can generate the new private key.
There are two requirements for the whole scenario:

User B should not be able to generate any of the user A's private key at any point.
User A and B can generate future public keys without even knowing their corresponding private keys.

The second part can be done easily if we have only one users:
$$S_{i} = S_{i-1}+X$$ then: $$P_{i} = P_{i-1}+X*G$$ So anyone who knows $X*G$ now can generate the next public key. So in the scenario that was mentioned, user B by giving part of $X$ should help user A to construct the next private key but then they cant know what the next public key will be since they both need to generate X and until then they cant generate $X*G$.
So the question is how we can make this work if user A needs some secrets from user B to construct the key pairs? (I assume we might need something similar to shamir secret sharing at some point)


texts: How to prevent accidental nonce reuse with AEAD cipher

texts:
I'm trying to correctly implement ChaCha20-Poly1305 in my node.js app (...crypto is hard). I understand that the cipher requires a unique key/nonce pair for each message or the security breaks down.

The nonce doesn't have to be random or unpredictable, so a simple counter is sufficient. My problem is that I can't figure out how to implement an efficient counter that will work with multiple instances of my app running simultaneously on the same machine and guarantee that no nonce will ever be reused.

Basically, I'm wondering how to avoid this footgun.

Some ideas I had:

Use a timestamp. Apparently not a great idea.
Use redis INCR. Complicates development environment (I now need redis installed on every computer I develop on), and I'm still left without strong guarantees that I won't get a duplicate value in case of an unexpected shutdown (even with Redis AOF).
Write to a file or database table every time a nonce is created. This should work, but the performance would not be great, and I'm probably still stuck in the event of an unexpected shutdown.
Use a UUIDv1 or v4 type thing (from the this comment). Initially v1 seemed perfect (guaranteed uniqueness), but it's tied to the system MAC address, so when I spin up multiple copies of the app, I'm probably killing any type of guarantee. Then there's v4, which should be good, but because the nonce is only 96 bits, I would need to truncate the ID and increase my collision probability (same goes for v1 actually). If I went this route, I was looking at nanoid.
Regularly rotate keys. I realize that this needs to be done anyway, but I want to minimize how often it needs to happen.
Something like Twitter's Snowflake. flake-idgen seems well suited for this (guaranteed uniqueness, partitioned by machine/worker or instance id, doesn't require coordination beyond determining instance ids, generates short enough ids).
Use XChaCha20-Poly1305. It's recommended in the libsodium docs specifically for this reason (the nonce is big enough that you can just throw random values at it and not worry). But, it's not a standard (yet?), and it would require bringing libsodium in for crypto instead of relying on node's built in OpenSSL wrapper. This complicates development (dealing with native bindings) and/or undermines security (constant time issues running crypto in js/WebAssembly...way over my pay grade).

Am I missing something obvious? How do people usually solve this kind of problem? Right now, I'm liking flake-idgen, but it doesn't seem like it's gotten a lot of scrutiny, so it seems possible that there are corner cases that could cause a duplicate id (leap seconds, leap year, accidental server clock reset, malicious NTP server, etc.).

Update: Ok, so the consensus seems to be to just use a random nonce and not worry too much about it. For my scale, I think that will be fine.

I found some issues in testing flake-idgen, so I don't think I would actually use that (although it still looks like a cool project).

My alternative plan would be to write a counter implementation that generates a 64bit BigInt counter (support added in Node 12) + a 16 bit instance ID + maybe 16 random bits for fun. I would persist the counter to disk after every X increments so that I'm not constantly writing to the disk. In the event of an unexpected server shutdown, the system would read from the disk file and add X + 1 to the current counter to ensure no-collisions.

Unsolved problems with this implementation: how to handle wrap around? what happens if the server is reset and there is no disk file to read from?

Thanks for your help on this, and if someone wants to post "just use random" as an answer, I'd be happy to accept it.


texts:
In AES algorithm, in the key schedule,
Why does the expansion of a 256 bit key need an extra application of the S-box, unlike the expansion of 128 bit and 192 bit keys ?

(The obvious answer would be "because it is more secure" ... but why ? And if it is more secure, why don't use it on 128 and 192 ?)


texts: How many Affine function can be made from $4 \times 4$ and $8 \times 8$ S-boxes?

texts:
The nonlinearity of an  S-Box is defined as the non-linearity of its vectorial Boolean Function.

Let $F$ be the hamming distance between the set of all non-constant linear combinations of component functions and the set of all $n$-variable affine Boolean functions $A(n)$.

If we take two S-Box of $4 \times 4$ and $8 \times 8$ then
how many Affine function can be made from $4 \times 4$ and $8 \times 8$ S-boxes ?


texts: Is this Sigma Protocol zero knowledge or is it just a proof of knowledge?

texts:
Suppose I have the witness $x$ and need to prove that I correctly computed $(g^x)^x$ to a verifier. $g$ and $g^x$ are public. The verifier asks me for $(g^x)^x$, but wants proof that I've given them the right answer.

Here's my attempt at a solution:

Let $X = g^x$ and $X' = (g^x)^x$

Step 1: Prover chooses a random $r$ and sends $R = g^r$ and $R' = X^r$

Step 2: Verifier sends a random $c$ (challenge)

Step 3: Prover sends $z = r + cx$ (response)

Step 4: Verifier checks if $g^z = RX^c$ and $X^z = R'(X')^c$.

I was wondering whether this is zero knowledge or just a proof of knowledge.

Thanks!


texts: Can CBC encryption have separate keys for separate blocks of plain text?

texts: Can we have separate key for separate blocks which we get while operating a plain text message  using CBC encryption model? If yes, what are it's advantage? Please enlighten me.


texts: Why is the whole initial state used in the final addition of Salsa20 and ChaCha?

texts:
Both Salsa20 and ChaCha basically work like this:

Put the key, the nonce, the sequence number and a constant into a 4x4 matrix of 32-bit words.
Transform the matrix invertibly with a number of ARX rounds.
Add the initial matrix into the current state to produce the output block.

Now, as discussed e.g. in this currently featured question, the final addition is required to prevent simple backwards computation from revealing the key. However, my question is: why is the whole initial matrix added in, rather than only the key part?

It seems that the addition of the rest of the matrix is mostly wasted effort, since they are publicly known numbers that an attacker with a known plaintext can simply subtract again.

On the other hand, there is a clear downside of extra memory and computation required. The latter is probably negligible compared to the whole cipher, but the former could be important, especially for hardware implementations. If only the key was added, the nonce and the sequence number would not need to be accessed again, saving a sixth of the state required (if you ignore constants).


texts: Performance consideration in XEdDSA and VXEdDSA Signature Schemes

texts:
Can someone please explain the below paragraph from section 7 in The XEdDSA and VXEdDSA Signature Schemes?

The below para states that we are hashing twice (I am not able to get that). How pre-hashing will help in this case.

  Pre-hashing: Except for XEdDSA verification, the signing and
  verification algorithms hash the input message twice. For large
  messages this could be expensive, and would require either large
  buffers or more complicated APIs.

  To prevent this, APIs may wish to specify a maximum message size that
  all implementations must be capable of buffering. Protocol designers
  can specify "pre-hashing" of message fields to fit within this.
  Designers are encouraged to use pre-hashing selectively, so as to
  limit the potential impact from collision attacks (e.g. pre-hashing
  the attachments to a message but not the message header or body).


texts: Why does the authenticated cipher CCM encrypt the MAC too?

texts:
Suppose I have Encryption in CTR-Mode and a CBC-MAC. Why should I also encrypt the MAC?

In the documentation of NIST stands: "By encrypting T we avoid CBC-MAC collision attacks".

But I can not imagine an attack based on an not-encrypted MAC.
Can anyone give me an example of such an attack?


texts:
Let H() be a hash function that achieves collision resistance

as well as first and second preimage resistance.

Let's equip the output set of H of a multiplicative group structure, more precisely a cyclic group.

The question

My question is: Is it hard, given $a$ to find $(b,c)$ such that $H(b) \times H(c) = H(a)$ ?

Heuristic / Intuition

Before trying a reduction to one of the hash properties, I tried to realize this function myself:

Given $a$, I take a random $b$, then I'm looking for $c$ satisfying:
$H(c) = H(a) \times H(b)^{-1}$.

Then preimage resistance of H prevent me from finding $c$.

Then my intuition is that my target function is as hard as preimage resistance, but I cannot end up

with a reduction: given $H(a)$ and an Oracle that solve my problem, I don't find a way to obtain $a$.

Identically, given such an Oracle I cannot find a way to create a collision.


texts: If $P \neq NP$ why doesn't this prove the existence of OWF?

texts:
i know that $P = NP \Rightarrow$ non existence of OWF.
but i don't understand why the claim:  $P \neq NP \Rightarrow$ existence of OWF is wrong?

An intuitive answer would be enough.


texts: How to perform a parallel hash over a large file without changing the sequential hash result?

texts: I want to use parallel hash for a large file. I want final result equal to single hash from this file. What techniques would be best suitable to solving this problem?


texts: How can we encrypt a text in Hill Cipher with a key matrix that is 3x3 when the plaintext is even like "ATTACKS"? Do we need to add padding like "x" or "z" to make the matrix equal? Thanks.


texts: Basic questions on how asymmetric keys "interact"

texts:
Have I understood this correctly?

To use a key and lock analogy. With an asymmetric pair of keys (when used to encode) can either key be used to encode the message (close the lock) and only the "pair" be used to decode (open the lock)?
Taking the key analogy further, is it a useful comparison to say that the first key of the pair changes the lock after it is used so that only the "not yet used" key of the asymmetric pair can open the lock?
The description of keys as "public" and "private" is only a convention that relates to their use and not the order in which they are used i.e. can use 3.1 public then private (encoding for one intended recipient) or 3.2 private then public (digital signatures)?

Edit: Wording of point 2 altered following comment by Maarten Bodewes.


texts: Constant time comparison for arrays of different lengths

texts:
I found the following code snippet from the Bouncy Castle C# library, which seems to claim that it's constant time, even when the arrays have different lengths.
/// <summary>
/// A constant time equals comparison - does not terminate early if
/// test will fail.
/// </summary>
/// <param name="a">first array</param>
/// <param name="b">second array</param>
/// <returns>true if arrays equal, false otherwise.</returns>
public static bool ConstantTimeAreEqual(byte[] a, byte[] b)
{
    if (null == a || null == b)
        return false;
    if (a == b)
        return true;

    int len = System.Math.Min(a.Length, b.Length);
    int nonEqual = a.Length ^ b.Length;
    for (int i = 0; i < len; ++i)
    {
        nonEqual |= (a[i] ^ b[i]);
    }
    for (int i = len; i < b.Length; ++i)
    {
        nonEqual |= (b[i] ^ ~b[i]);
    }
    return 0 == nonEqual;
}

However, I've heard that it's not possible to compare arrays of different sizes in constant time. For instance, the Go crypto ConstantTimeCompare() function checks the length of the arrays before the comparison. Some people have complained that this leaks the length of the secret.
func ConstantTimeCompare(x, y []byte) int {
    if len(x) != len(y) { // <--- here
        return 0
    }

    var v byte

    for i := 0; i < len(x); i++ {
        v |= x[i] ^ y[i]
    }

    return ConstantTimeByteEq(v, 0)
}

Which approach should be taken when comparing arrays of different lengths? Or should you just hash the data and then perform the comparison (since the lengths will be the same)?


texts: Deterministic Key using a seed for ECNamedCurve

texts:
I am trying to generate deterministic keys using EC curve secp521r1 in java. I went through KDF but, couldn't find any references to use it with EC curves. I would appreciate if someone could point me to KDF or something similar to it for deterministic EC keys. All I need is to generate EC key pair using a passpharse.
Sample code that I am using to generate EC keys in Java:
 ECParameterSpec ecSpec = ECNamedCurveTable.getParameterSpec("secp521r1");
        KeyPairGenerator g = KeyPairGenerator.getInstance("ECDSA", "BC");

        g.initialize(ecSpec, new SecureRandom());
        KeyPair pair = g.generateKeyPair();

        KeyFactory fact = KeyFactory.getInstance("ECDSA", "BC");
        PublicKey pub = fact.generatePublic(new X509EncodedKeySpec(pair.getPublic().getEncoded()));
        PrivateKey priv = fact.generatePrivate(new PKCS8EncodedKeySpec(pair.getPrivate().getEncoded()));


texts: Derive a key from public data using a secret master key

texts:
Users in my system will be given a device that contains a 128-bit AES user key. The user key will be derived from 64 bits of public data related to the user, which is unique but very predictable (i.e. a sequential user ID value). The value of the user key must be kept secret from the users. I assume users are fully aware that the user ID is used in the key derivation and that they know its value. A centrally controlled "master" AES key will be used to derive the user key in each device. Users will have no access to this key.

I've been asked to design the derivation scheme. The goal is to ensure the user has no hope of determining their key based on the 64-bits of public data.

My current plan for this derivation is to concatenate a "context" byte to the user ID and then encrypt it with the master key, using ECB-mode and PKCS #7 padding and use the result as the user key.

Does this simplistic derivation scheme meet my design goal? Without knowledge of the master key, I can't fathom how users could infer anything about the user key from the public data. However the simplicity of my design worries me.

I have encountered key derivation schemes, such as RFC 5869 that might be appropriate. I would be much happier using a peer-reviewed method rather than designing my own if someone can point at a suitable standard.


texts: How to disperse personal data before returning?

texts:
I am working on a project that is dealing with personal data.
The task is to find a method such that when user makes a query into multiple institutions, the result will contain already scattered/dispersed data.
I'll try to give an example:

The user asks data from institution A and institution B. User sends
the query: "Find all persons whose age is between 20 and 30 AND has net income over 3000£ a week".
Then institutions sends back data in aggregated form, like "there are 443 persons whose age is between 20 and 30 and net income is <= 3000£."
Or institutions send back dispersed / scattered data without personal information where personal information is hidden.

The main idea is to prevent sending original data out from institutions.
So I am wondering is there any algorithm or any other method that can be used to hide or make this kind of scenario possible?
I have come across with secure multiparty computation and some fragment algorithms, but would like to hear more options.


texts: passive corruption ?= Byzantine corruption in the UC framework?

texts:
Notations: We follow the convention in the UC framework. We use $\mathcal{A}$ to denote the adversary, $\mathcal{P}$ to denote a party in the model.

We focus on two types of corruption in the UC framework, which we rephrase now.

Byzantine corruption: $\mathcal{A}$ takes the full control of $\mathcal{P}$.
Passive corruption: $\mathcal{A}$ sees the internal state of $\mathcal{P}$.

My question is:

  Is passive corruption actually equivalent to Byzantine corruption?

Now I explain the reason behind my question.

In the UC framework, $\mathcal{A}$ controls the network, if $\mathcal{A}$ only has the ability to see the internal state of $\mathcal{P}$, $\mathcal{A}$ can do the following to approximate "controlling $\mathcal{P}$" in the real-world model:

$\mathcal{A}$ isolates $\mathcal{P}$ from the network.
$\mathcal{A}$ copies the internal state of $\mathcal{P}$ and launches a virtual machine $\widetilde{\mathcal{P}}$.
$\widetilde{\mathcal{P}}$ has the same internal state as $\mathcal{P}$ at the time of corruption. But, $\mathcal{A}$ takes the full control of $\widetilde{\mathcal{P}}$.
$\widetilde{\mathcal{P}}$ pretends to be $\mathcal{P}$ in the rest of the execution.

Some readers may suspect whether 4 is possible in the UC framework with authenticated channels. Now I explain my concerns.

In the UC framework, it is non-trivial to know who actually sends the message. We need to rely on "authenticated channels". We use $\mathcal{F}_\mathsf{auth}$ to denote the ideal functionality for such a communication channel.

Via $\mathcal{F}_\mathsf{auth}$, parties in the protocol can make sure who sends the message. If $\mathcal{P}$ is Byzantinely corrupted by $\mathcal{A}$, $\mathcal{A}$ can send messages in the name of $\mathcal{P}$.

But, what if $\mathcal{A}$ passively corrupt $\mathcal{P}$?

The definition of $\mathcal{F}_\mathsf{auth}$ allows $\mathcal{A}$ to change the messages sending out from $\mathcal{P}$ if $\mathcal{A}$ corrupts $\mathcal{P}$. It is not clear whether it differs in the case of  passive corruption.
Existing realizations of $\mathcal{F}_\mathsf{auth}$ rely on some secrets in $\mathcal{P}$, such as the signing key. If $\mathcal{A}$ just sees the internal state of $\mathcal{P}$, which includes such secrets, then $\mathcal{A}$ can pretend to be $\mathcal{P}$ in these realizations.

Or in other words, passive corruption does not reduce $\mathcal{A}$'s ability to impersonate $\mathcal{P}$.

Back to my question:

  Is passive corruption actually equivalent to Byzantine corruption?

And a followed-up question.

  How should I model something similar to passive corruption?

Thanks for your reading.

Let me add an example to assist explanation.

Consider that I can passively corrupt the webserver of CVS. I can steal their TLS/SSL certificate private keys in the CVS webserver's internal state.

Then, I make a man-in-the-middle attack to a specific client, and if I also control the network, I can mimic CVS website to this client and display wrong pharmacy records.

Reference:

Canetti's paper on the UC framework. "Universally Composable Security: A New Paradigm for Cryptographic Protocols".
https://eprint.iacr.org/2000/067.pdf
Canetti's paper on realizing $\mathcal{F}_\mathsf{auth}$ using $\mathcal{F}_\mathsf{sig}$. "Universally Composable Signature, Certification, and Authentication". https://eprint.iacr.org/2003/239.pdf
Canetti-Shahaf-Vald's paper on realizing $\mathcal{F}_\mathsf{auth}$ with a global PKI (a bulletin-board certificate authority) also using $\mathcal{F}_\mathsf{sig}$. "Universally Composable Authentication and Key-exchange with
Global PKI". https://eprint.iacr.org/2014/432.pdf
Backes-Pfitzmann-Waidner's paper on realizing $\mathcal{F}_\mathsf{sig}$ with a public-key signing scheme. "A Universally Composable Cryptographic Library". https://eprint.iacr.org/2003/015.pdf


texts:
The $Sage$ code for the AES $S-box$ is below and a link is here: Polynomial representation of the affine part of the AES S-box. An online version of $Sage$ to test this is here.

I understand most of it but I cannot understand where the polynomials for $a$ to $h$ come from. Can anyone give a simple example? Even for just one of the polynomials if this will suffice.


texts: A qusetion about the security game of Certificateless signatures

texts:
Recently I read Certificateless Public Auditing for Data Integrity in the Cloud , I have a question about the security of proposed HOMOMORPHIC AUTHENTICABLE CLS. （Sec. IV）. For the Type-I Adversary, in the forgery phase, the authors said ,

however if $${H_1}(I{D_s}) = {({P^b})^r}$$ , which means the coin shows 0. If the coin is 0, F outputs $ \bot $  , so how does this forgery $\sigma $ comes from?


texts: How Are Linear Congruential Generator Multipliers Chosen?

texts:
There are several numbers that keep coming up when looking at certain random number generators, for example 6364136223846793005 is used in newer pcg-family algorithms and seems to draw it from mt19937_64.

How are these numbers chosen? What are their relevance to generation of random values?


texts: Understanding public key cryptography example

texts:
Frankly, I wasn't sure whether this belongs in crypto.stackexchange.com or here, so forgive me. I've been going through a book where in one of the chapters the author tries to illustrate public key cryptography by imagining a "four-step business plan for Murder Incorporated" in a "world of strong privacy".

Arrange for mystery billboards on major highways. Each contains a
single long number and the message “write this down.” Display ads with
the same message appear in major newspapers.

Put a full-page ad in the New York Times, apparently written in
gibberish.

Arrange a multiple assassination with high-profile targets, such as
film stars or major sports figures – perhaps a bomb at the Academy
Awards.

Send a message to all major media outlets telling them that the number
on all of those bulletin boards is a public key. If they use it to
decrypt the New York Times ad they will get a description of the
assassination, published the day before it happened.

I don't quite understand the mechanics of how the outlets are able to decrypt the ad and get a description of the assassination. Is the ad encrypted with his private key and since both public and the private keys are mathematically related, whatever is encrypted with the private key can be decrypted with the public key (visible on the billboard) and vice versa?


texts: Determining Involutary Keys in Substitution Ciphers

texts:
How would I be able to show that a key $K=(a,b)$ is involutary for an Affine Cipher over the integers modulo n?

Similarly, is there a way to generalize the conditions for a key to be involutary for a substitution cipher?

(Involutary keys are keys for which the encryption function is equal to the decryption function $e_K=d_K$)


texts: How can a public-key encryption scheme be used to construct a commitment scheme in the CRS model?

texts:
For a PKE scheme $(Gen, Enc, Dec)$, the most 'obvious' idea is to commit to an encryption of a bit and in the reveal phase maybe send $r_g$, $r_e$ where $r_g$ is the randomness of $Gen$ and $r_e$ is the randomness of $Enc$.

However, if the encryption scheme is not perfectly correct, then maybe there is some $sk, sk'$ such that $Dec(sk, c) = 0$ and $Dec(sk', c) = 1$, so binding fails, because we can fiddle with $r_1$.

A solution is to only reveal $r_2$, and then in revealing one only needs to check that $Enc(pk, b, r_2) = c$. Particularly, if the probability over $Gen$ that there exists some $r_2, r_2'$ with $Enc(pk, b, r_2) = Enc(pk, 1-b, r_2')$ is negligible, then this almost works. However since the sender doesn't have to prove what $sk$ they used, we can still break binding.

How can we get around this issue in the CRS model?


texts: Digital Signature or MAC Yielding Non-Binary Verification Predicate

texts:
Is there a digital signature or MAC scheme in which, the verification algorithm returns not $\{\text{Valid},\text{Invalid}\}$, but a discrete (finite or infinite) set of result such as $\{\text{Valid-for-A}, \text{Valid-for-B}, \text{Valid-for-C}, \text{Invalid-for-All}\}$?
This is a curiosity question. There is no limit on the nature of the scheme, it can be symmetric or asymmetric, classical, or post-quantum.
EDIT
To explain why could potentially be "Valid-for-{A,B,C}":

In PKC there could be 3 (or any number of) private keys derived from a master private key (possibly using some form of key-escrow), that can be identified and verified by the "master" public key. An application of such scheme could be "bandwidth-efficient group member authentication".

In symmetric-key cryptography, it could be an multi-party broadcast domain authenticated encryption, in which ciphertext verification don't require computing the tag with each of the peers' key - the recipiant instead somehow use the shared key to "decrypt" or "derive" the peer's key. Same application as above.


texts: What information to include is the 'info' input for HKDF?

texts:
The RFC states the following:

  3.2.  The 'info' Input to HKDF

  While the 'info' value is optional in the definition of HKDF, it is often of great importance in applications.  Its main objective is to bind the derived key material to application- and context-specific information.  For example, 'info' may contain a protocol number, algorithm identifiers, user identities, etc.  In particular, it may prevent the derivation of the same keying material for different contexts (when the same input key material (IKM) is used in such different contexts).  It may also accommodate additional inputs to the key expansion part, if so desired (e.g., an application may want to bind the key material to its length L, thus making L part of the 'info' field).  There is one technical requirement from 'info': it should be independent of the input key material value IKM.

I'm still a little bit unclear on how to use this input.  Does the 'info' input function as somewhat of a salt?  If I'm developing a multi-user application, and each user:

uses HKDF to expand 16+ psuedo-random byes into a larger key
has a unique email address
uses the expanded key for a specific algorithm of their choosing

Would it be appropriate to use the user's email address, and the name of the algorithm for which the key will be used? Any analogies for better understanding the usage of this input would be appreciated.


texts: How can we implement a PRF with 1bit input space and 1024bit output space using AES securely?

texts:
I'm considering an implementation of PRF
$F:\{0,1\} \times \mathcal{K} \rightarrow \{0,1\}^{1024}$ with a key space $\mathcal{K}$ in particular with AES-128 in counter mode.

Since output space is 1024 bit and one block size is 128 bit, we need to use 8 blocks to encrypt a counter and a nonce.
The counter is incremented in some way every time a block encryption is finished.
Then, an input $m$ is XORed to each of the encrypted blocks.
So a string that concatenates 8 encrypted blocks is considered as an output of the function.

Is this secure? Any correlation between two encrypted blocks?


texts: What's wrong with this construction? ECDHE+AES

texts:
Let's say I want to use ECs to do asymmetric encryption. Suppose both sides have generated EC keypairs and have exchanged their public keys. I run ECDHE, and get a derived secret. I would then either use that as a key for AES, or create a derived key with an incrementing nonce for subsequent "sessions".

My gut tells me rolling my own is a bad idea. Not having seen this construct implemented in any crypto library tells me it's an even worse idea. Is there a concrete flaw in what I've described above?


texts:
In RSA, the $p$ and $q$ should be randomly generated, and they are the same size. The difference between $p$ and $q$ should not be small.

Suppose that $u=|p-q|<20$ and $p \times q =2189284635403183$. Find the values of $p$ and $q$.

I have no idea how to compute $p$ and $q$. I use calculator to compute square root of thr product. But it is definitely not correct as I get something ends with $2$. Can anyone help me?


texts: Hardness of problem related to bilinear pairings

texts:
Let $e: \mathbb G_1 \times \mathbb G_1 \rightarrow \mathbb G_T$ be an efficient bilinear pairing. Note that the pairing is symmetric (i.e., Type 1).

The problem is, given $g \in \mathbb G_1$ and $e(g,g)^a \in \mathbb G_T$, for an unknown $a$,  to compute $X_1, X_2 \in \mathbb G_1$ such that $e(X_1,X_2) = e(g,g)^a$

Is this a hard problem? My feeling is that it is not and there should be an easy way to solve it.

Update 1: I have found a related problem that it is said to be hard:

  The Pairing Pre-Image Problem (PPIP) in $\mathbb G_1, \mathbb G_T$
  such that $\mathbb G_1 = <g>, |\mathbb G_1| = |\mathbb G_T | = p$ with
  pairing $e : \mathbb G_1 \times \mathbb G_1 \rightarrow \mathbb G_T$
  is defined as follows: On input a tuple $(g, Z) \in \mathbb G_1 \times$
  $\mathbb G_T$, output $X \in \mathbb G_1$ such that $e(X, g) = Z$.

According to this paper:
 CDH in $\mathbb G_1 \leq$ PPIP $\leq$ DL $\in \mathbb G_T$

The problem I am asking is not harder than PPIP since I could use PPIP to solve my problem : simply run the PPIP solver on $(g,Z)$, take output $X$, and return $X_1 = X, X_2 = g$. That is, PPIP is my problem but requiring that $X_2=g$.

Still, I think that there should be an easy way to solve my problem. Any ideas?

Update 2: Thanks to the comment from @DrLecter, now I know that the original problem I stated was exactly the Generalized Pairing Inversion (GPI) problem, which seems to be hard. That makes me reformulate the question to my real problem (see this question).


texts: Is double SHA-256 the best choice for Bitcoin?

texts:
So I was just curious.
I really look up to Blockchain technology and I have read that Bitcoin uses double SHA-256 for hashing.
( from what I understood, double sha256 is essentially $\operatorname{SHA-256}(\operatorname{SHA256}(value))$ ).
Is double SHA-256 better than SHA-512 or any other hashing algorithm that bitcoin could use? Or maybe there are other alternatives that could bring some benefits over the double SHA-256 for bitcoin?


texts: Montgomery Multiplication in FPGA explanation

texts:
I'm trying to implement an RSA module in a FPGA. I choose to use Montgomery multiplication. I've found a document where the Montgomery Multiplication is pretty clear. I don't understand only a step.

The algorithm is…

$S[0] = 0\\
for\ i\ to\ (k-1)\ loop\\
\ \ \ \ q_{i} = ( S[i]_0 + A_{i} \times{B_{0}} ) \bmod{2}\\
\ \ \ \ S[i+1] = (S[i] + A_{i} \times{B} + q_{i} \times{n} ) \div{2}\\
end\ loop$

… where $w$ is word length, $A$ and $B$ are the factors, and $S$ is the result.

If $q_{i}$ is only one bit (as far I understood), why does it use the operator “$\bmod{2}$”? What am I missing?


texts: In my opinion a lot of encryption paper have small contribution in terms of security improvements

texts:
I used to saw a lot of encryption papers that have small significance in security improvements especially in terms of entropy, histogram and coefficient correlation especially in image encryption. Why is this happening?i mean why still publish a proposed method that have 0.001 or so on improvement in terms of entropy or coefficient correlation?even some of the papers does not tell how it significantly differs in terms of security.
for example in this paper, in terms of entropy and npcr uaci it does not have significant improvement compared to the referenced paper.. like in entropy value it only have 0.001 difference to ref 33 and 34 and also in npcr uaci only 0.01 difference.. i know its value is close to the ideal value hence it can resist entropy attack and so on, but why make another proposed method with no significant contribution in the security?is it just for encryption method variation?i am new in cryptography, please help enlighten me


texts: Can adding bad entropy to good entropy, make a system insecure?

texts:
For example,

If I needed to generate a random number. I use a good source of entropy to generate r.

Then I add values a, b and c whom are generated from bad entropy such that new entropy = r + a + b + c

How would the overall entropy look like?

The plus sign means to add and not concatenate. I believe that if we concatenated, then this would lead to an overall bad entropy because if we assume that each a,b,c,r each contribute 64 bits to 256 bits of entropy. We would in reality only have 64 bits of good entropy from r. This is my intuition with concatenation.


texts: proving indistinguishability of joint distribution using hybrid argument

texts:
Using Hybrid Argument, I want to prove following equivalence:
$$\{X,Y,Z\}\equiv \{X',Y',Z'\}$$

by proving following equivalences:
$\{X,Y,Z\}\equiv \{X,Y,Z'\}$(1)
$\{X,Y,Z'\}\equiv \{X,Y',Z'\}$(2)
$\{X,Y',Z'\}\equiv \{X',Y',Z'\}$ (3)
I know how to prove $\{Z\}\equiv\{Z'\}$, under what condition $\{Z\}\equiv\{Z'\}$ implies (1) ?

(I've changed my post since my problem has nothing to do with SMC (maybe it has nothing to do with cryptography either) and the way I presented the problem was confusing. )


texts: How comparable is OFB to a one-time pad?

texts:
This is a rather trivial question, I just want to see if I get the concept right.

In OFB you generate a pseudorandom stream based on some nonce, and you XOR that with the message to get the ciphertext. This sounds a lot like a one-time pad but I don't see the parallelism anywhere in literature. Am I missing something?


texts: How does the ring settings of enigma change wiring tables?

texts:
EDIT: The model I'm trying to make is "Enigma 1". I learned initially about it from a book called "Code Book" and then looked at it in detail from its wikipedia page. The site wont allow me too add more links but google "enigma rotor details" and see the wikipedia page

There is a similarly worded question here but it doesn't answer mine.

I am trying to make an enigma simulator. I have finished doing everything except the ring settings. How do they affect the substitutions?

For example suppose the initial rotor settings are:

abcdefghijklmnopqrstuvwxyz
ekmflgdqvzntowyhxuspaibrcj

I think by applying the ring setting of B or 2, the settings should become:

abcdefghijklmnopqrstuvwxyz
kmflgdqvzntowyhxuspaibrcje

I think all I should have to do is add the ring positions to the rotor positions. But that doesn't seem to be the case.
I tried decrypting the first sample message from here that way but didn't succeed. I even tried to make the program run in a loop till it finds the intended answer so I could deduce the relation between ring settings and rotor positions, but it never found it.

But using the same settings on an online enigma simulator worked. Everything seems to be the same except that according to the online simulator, the rotor wirings on a ring setting of b or 2 should be:

abcdefghijklmnopqrstuvwxyz
kflngmherwaoupxziyvtqbjcsd

How on earth did it turn into that?


texts: Is scrypt a hashing function, encryption, or PBKDF?

texts: I have installed a python implementation of scrypt and noticed it has several functions, both an encrypt and hash function. Yet Wikipedia lists it as being used for PBKDF instead of PBKDF2. Is scrypt a hashing function for PBKDF2 or is it on its own an alternative?


texts:
I'm trying to understand why the secret keys used by Alice and Bob in Diffie-Hellman are $a,b ∈ ℤ∗p$.

Say $a$ is $p - 1$, wouldn't the transmitted $g^a$ be 1 mod $p$ by $FLT$? Now anytime a passive listener sees a 1 being transmitted would know one of the secret keys and could easily compute the message. I'm sure I'm missing something obvious but I can't figure it out.


texts:
I have seen some applications use key expansion when deriving AES-keys.
E.g. the application will generate some random data (e.g. 128bits), then use PBKDF2 to expand it into 512bits (2x256 keys).

Why go through this process of taking a small amount of random and expanding it, instead of taking 512bits cryptographic randomness directly?

The random 'seed' value is not stored either so it can be reused for the key expansion.


texts: RSA - How to change the encrypted numerical result into text?

texts:
I'm aware of the way that the original plain text is converted into a number by taking the ascii numbers of the byte array of the plain text, but doing things the other way around doesn't seem to work.

The encrypted message is pretty much a series of random digits(let's say it's in hexadecimal), which means that some of it will go above the 7F, or 127, limit of ascii. What happens then?

Edit: Ah, my error was that I somehow forgot that ascii was just 7 bits. Anyway, it was useful seeing how the ciphertext can be represented in different ways.


texts: Attribute-based broadcast encryption with respect to ABE

texts:
What is the exact difference between attribute-based encryption (ABE) and attribute-based broadcast encryption (ABBE)?
Is ABBE equivalent to broadcast encryption on top of ABE?


texts: What parts of AES encryption result are safe to pass on the network

texts:
I'm using AES to encrypt the message.
both sender and receiver know the passphrase, but only sender knows IV and salt

I assume that receiver also needs to know IV and salt to decypher text;

is it safe to pass IV and salt along with the cyphertext over an unsecured network, or will this compromise the security?

I'm using https://code.google.com/p/crypto-js to send encrypted messages between multiple clients.


texts: Can I secure my key by XORing it with a hashed password?

texts:
I'd like to build a simple password-protected symmetric key system.  The key-creation process in my system operates as follows:

The system creates a 256-bit key purely at random.
The user chooses a password, which is hashed using SHA-256.
The system stores the value key XOR SHA(password), which we call the "pseudo-key".

The pseudo-key is stored permanently by the system or user, whereas the actual key and password hash are never stored. When the user wants to produce his key for encryption or decryption, he can recreate the actual key from pseudokey XOR SHA(password). The password hash and actual key are always destroyed immediately after use.

Aside from an adversary obtaining the pseudo-key and brute-forcing the password, are there any obvious theoretical problems with this system?
Is it notably inferior to other extant password-based key systems?
Is the system I'm describing (or any system that password-protects a symmetric key) already present in some cryptographic library?


texts: How to calculate time needed for decryption of 64-bit key

texts: I am having trouble figuring out how long it takes to decrypt a 64-bit key, given that a computer can do 1 billion trials per second. I know that there are $2^{64} = 1.844 \times 10^{19}$ possible keys for this key size, but then how do I go about figuring out the rest? If there is a formula for this, I would be very curious to know what it is.


texts: Multivariate cryptography - easily invertible quadratic map

texts:
I am reading through multivariate cryptography and in every source I have seen, the secret map $P$ is described as "easily invertible" or "easy to invert".

What exactly does it mean "easily invertible"?


texts: Why are security against eavesdropping and security against CPA equivalent in the setting of public-key cryptography?


texts: Cryptographic limit to total accounts in secp256k1

texts:
Factoring in birth day attacks and all that, with 256-bit elliptic curve cryptography, lets take secp256k1 as example that Bitcoin uses, what is the maximum number of accounts that are secure? It isn't $2^{256}$ since then any time you generate a random number you find a used account.
Birth day paradox and all that, what is the upper limit of how many accounts secp256k1 actually supports?


texts: How does Web Cryptography API produce secure PRNG?

texts:
How does Web Cryptography API (eg window.crypto.getRandomValues) produce secure PRNG?

Specifications:

https://dvcs.w3.org/hg/webcrypto-api/raw-file/tip/spec/Overview.html#RandomSource-interface
https://developer.mozilla.org/en-US/docs/Web/API/window.crypto.getRandomValues

How can the method be trusted? Or is it event trustworthy?


texts: Integer factorization still hard with Hamming weight hypothesis?

texts:
Consider the following problem:

Factorize a $n$-bit integer $c$ knowing that it is the product of two integers with known Hamming weight $h$.

Is there a way to prove that this is still hard? I have parameters $n=1024$ and $h=80$, but am willing to augment $h$ if this turns out to be easy. I think this problem is current-factorization-algorithms-related, since I did not find an easy way to describe the distribution of these type of numbers (my try considered quadratic expressions of dependent Bernoulli trials). So the question may be reformulated: Does this hypothesis helps any of the actual factorization algorithms?


texts:
In the course I'm studying, if I've understood it right, the main difference between the two is supposed to be that finite fields have division (inverse multiplication) while rings don't. But as I remember, rings also had inverse multiplication, so I can't see any difference.

What is the main difference between finite fields and rings?


texts: Euler's Totient function for semiprime numbers

texts:
I have noticed, during the period I spent studying RSA, that Euler's Totient function can be calculated in another way than $ϕ(N) =(p-1).(q-1)$

Let me explain myself by pointing to a brief example:

$p = 131$

$q = 11953$

$N= p*q = 1565843$

The totient defines the quantity of positive integers less or equal than $N$ coprime with $N$. So we calculate it:

$ϕ(N) = (p-1)(q-1) = 1553760$

But I have realized that this way can also be obtained:

How many multiples of p are under N? q multiples of p

How many multiples of q are under N? p multiples of q

These previous statements show the quantity of integers NOT coprime with $N$ that are less or equal to $N$. It's just the opposite of the Euler's Totient.

So the equation is the following:

$ϕ(N) = N - p - q + 1$

In the example:

$ϕ(N) = 1565843 - 131 - 11953 + 1$

$ϕ(N) = 1553760$

I suppose that this method is well documented over there. I just want to know if this is a good praxis for using in an implementation (for example).

Thanks for your time!


texts: Is it possible to construct a secure block cipher of size $2n$ given a secure block cipher of size $n$?

texts:
Given, say, the Blowfish block cipher, which is considered secure but only has a 64-bit block size, can we construct a secure block cipher of 128-bit block size?

Say we run the key through two KDFs, and encrypt the first half of the block with the first key, and the second half of the block with the second key. This seems to give a 128-bit block cipher. However, this is probably insecure, since say if we use CTR mode both halves still become insecure by themselves.


texts: Encrypting cryptocurrency seeds for cold storage

texts:
I’d like some feedback on an encrypting algorithm. I’m not rolling my own, but even putting together well-proved pieces may create many pitfalls. (I don’t know if I'm stretching questioning in this forum. I'm after concrete feedback on concrete, potential pitfalls.)
The purpose:

Cold storage of encrypted cryptocurrency seeds (i.e. secret keys).

EDIT: The seed (as used in this question) is the super secret plaintext. But often called seeds, as it is normally a binary array, and not ascii.
The purpose is the same as for BIP0038 (* see summary below).
Likelihood of someone reusing a passphrase is definitely present.
The algorithm should be as simple as possible, to avoid errors in implementations.
My proposal:

Generate cryptographically random seed (32 bytes) (Or input from user*)
* EDIT: The seed is 32 random bytes. User may input a cryptographically random seed, generated somewhere else, if she wants to. The seed is used to generate public addresses. A bit like private/public key pairs. It's the private key, the seed, that I would like to encrypt and store.)
Input UTF-8 passphrase from user, applying canonical normalization
Generate cryptographically random salt (12 bytes)
(Possibly ask for an input on “toughness”, to adjust the argon2id parameters.)

.

Generate 32 byte encryption key, using Argon2id, using 2) and 3).
I guess the argon2id options is a separate topic altogether.
I think iterations = 2(something + toughness)

.

Encrypt the seed 1) with AES-CTR, using salt from 3) as counter, and encryption key from 5).

Encrypted seed (6) + Salt (3) is concatenated and base32 encoded to uppercase, to make the most compact QR code, appended by ‘:T’ + <toughness>.

.
My reasoning and Questions
Any tripwires I’ve tangled myself into?
AES-GCM is preferred over AES-CTR.
GCM has message authentication. But I don’t see mallability as an attack vector. You might as well burn the piece of paper, instead of scribbling on the QR code.
A) Are GCM and CTR equally good in this use-case?
Both have a catastrophic failure if the same key and counter is re-used.   (No difference there, that I am aware.)
B) Birthday problem. Why 12 byte salt?
Open for input. :)
Reading Birthday attack - Wikipedia, and if my math is correct:
An 8 byte salt would yield a likely birthday collision every 5x10^9 reuse of the passphrase.
A 12 byte salt would yield a likely birthday collision every 3x10^14 reuse of the passphrase.
But it will fit in the same size QR code, after base32 encoded. (Version 3, ECC level L.)
C) A 16 byte salt is still better. But is it needed?
Any considerations regarding Argon2id?
D) Is there a problem that the salt is reused for two different operations? (Both Argon2id and AES)
E) AES CTR vs CBC? The seed is 32 bytes long, so no padding is needed for CBC.  Both need a random counter/iv.  Are they equally good for this use-case, or does one of them have a better fit for the problem?
Why base32? Because QR has an optimized encoding for uppercase and digits. And security here is more than hacking. An unreadable QR code is just as disastrous.
Keepass is all very good for this too.
My use-case is scannable paper. And that my wife can use it if I get hit by a bus or fall off a cliff. :)
I apologize if this post being a bit long.  But it's putting the steps together that causes the security to break.
Any comment are welcoming. :)
vbakke
.
* The BIP38. https://en.bitcoin.it/wiki/BIP_0038 Uses scrypt, and 2xsha-ing the passphrase first. The salt derives from the passphrase, so reusing the passphrase is an issue.
BIP38 feels overly complicated. Like someone tying lots of bad knots, instead of tying one knot properly to secure the load. Simplicity is also security.


texts: libsodium vs gnupg curve25519 compatibility

texts:
I am trying to create deterministic GPG keys based on cryptosteel. I have implemented a library for (de)serializing PGP packets and am now trying to use keys generated in libsodium for import in GPG.

Libsodium gives me a 32-byte public key and a 32-byte secret key. This is also what PGP seems to use - except PGP prefixes 0x40 to the public key to indicate it isn't using point compression (and thus becomes 33 bytes).

ed25519 keys work fine, but curve25519 keys don't work, when trying to import the generated key GPG asks for a passphrase - despite not specifying a KDF. It seems the points generated by libsodium are not compatible with GPG.

A few random things I don't understand, that may be related to this:
- GPG points are 32 bytes, but they are uncompressed. Shouldn't they be 32 + 32 bytes then? From all I can read it seems both X and Y should be 32 bytes.
- Libsodium might be using compressed points, but their points don't start with 02 or 03 - which I read is used to indicate which Y was taken for the key. They are also 32 bytes, which would also be too small if you consider an extra byte to indicate the compression.

Does anybody know what exactly is different between these curves and what I could do to fix it?


texts: Implement deniable encryption with AES/RSA

texts:
I'm on a crypto app using OpenSSL (I'm more an implementer/cryptographer than a cryptologist), mainly as a hobby, for now.

My app will be able to encrypt a file (not a container) with symmetric or asymmetric or both encryption (sym then asym), and I want to implement "deniable encryption" (I'm in France, you should have heard about the law which has just been voted: our NSA now has all rights on internet).

My first issue is RSA: for example, when decrypting with a wrong key, it fails to leave a correct padding. So, a file won't be decrypted to a random looking badly deciphered text. I hope a symmetric algorithm will allow me to do that, but first I'm using RSA. Do any of you have an idea on how to "force" RSA to decrypt a file to a valid message (but not the cleartext), allowing a user to claim it was the right key? I assume that the protocol will be known.

If possible I would also be interested in suggestions of other methods with this "behaviour", or implementations of this.

EDIT: Precision: The cryptosystem*will be able to encrypt a cleartext with public-key (which implies symmetric encryption) OR symmetric encryption OR (minor probability) both one after the other (for i.e.: Let's say you have an already symmetric ciphered file you need to relay, you can apply a public-key encryption, which will make the file encrypted twice with probably 2 different algorithms and 2 different keys).

PS: Redirected to chat, too many comments.


texts: Why does openssl use SHA1 in ECC when I use secp384r1 curve

texts:
I need a small clarification that why openssl using SHA1 in ECC when I am using secp384r1 curve, but in rfc they are saying we should use SHA2.

Thing here is am using nanoECC in my DTLS, nanoECC using SHA384 for secp384r1 but openssl is using SHA1. So which one to use, if openssl is wrong then how to set openssl to use SHA384 for secp384r1 curve.


texts:
I found from a book the following proof.

Although I understand the initial construction, I don't understand the last sentence that proves the statement.

Why $f(f(x))$, in the paper $h(h(x))$, is always equal to $0^{2n}$
Is this what they are saying?
Why is it clearly not a one way function?


texts: LWE: does using only a small subspace of the plaintext space influence the security of the encryption scheme?

texts:
Regarding LWE schemes where the encryption is performed this way:

for $m \in \mathbb{Z}_t$, compute $c = LWE_{\mathbf{s}}^{t/q}(m) = \{ \mathbf{a}, \mathbf{a \cdot s} + m\cdot q/t + e\} \in \mathbb{Z}_{q}^{n}$

(where $\mathbf{s}$ is the secret vector of length $n$, $\mathbf{a}$ is a random vector and $e$ is some noise generated by a discrete Gaussian sampler)

What happens if for a given plaintext modulus $t$, we use only a small subspace of $Z_t$ for our messages? Does it have any influence on the overall security of the scheme?


texts: Number of functions included in a keyed PRF

texts:
I was reading Introduction to Modern Cryptography by Katz and Lindell and i found this:

  Coming back to our discussion of pseudorandom functions, recall that a
  pseudorandom function is a keyed function F such that $F_k$ (for $k\in2 \{0, 1\}^n$
  chosen uniformly at random) is indistinguishable from $f$ (for $f\in$ $Func_n$ chosen
  uniformly at random). The former is chosen from a distribution over (at most)
  $2^n$ distinct functions, whereas the latter is chosen from all $2^{n*2n}$
  functions in
  Funcn. Despite this, the “behavior” of these functions must look the same to
  any polynomial-time distinguisher.

How did he got into the conclusion that keyed function F is chosen over $2^n$ distinct functions?

Does he assume that there is a fixed function which maybe differentiated by the key k, so total of $2^n$ "functions"?


texts: Linear Recurrence, keystreams, and periods

texts:
I am trying to understand the following problem:

  Consider the following linear recurrence over $Z_2$ of degree four:

  $z_{i+4} = (z_{i+3} + z_{i+2} + z_{i+1} + z_{i}) \bmod 2$

  i >= 0. For each of the 16 possible initialization vectors
  ($z_0$,$z_1$,$z_1$,$z_4$) in ($Z_2)^4$, determine the period of the
  resulting keystream.

  What does it mean by the 16 possible initialization vectors? Are there just (0,0,0,0) (0,0,0,1) (0,0,1,0) (0,0,1,1) etc..?
  How do I use these initialization vectors in the formula it gives


texts:
I am using C and OpenSSL to encrypt files. After experimenting with the OpenSSL command line utility, it makes you enter a passphrase that can be any length, but uses that to create a 256-bit key.

How many passwords or keys does aes use & how does it use them? If you can make your passphrase as long or as short as you want, what is the point of having a 256-bit encryption?


texts: How was the special DES key 0E329232EA6D0D73 found?

texts:
The DES key 0E329232EA6D0D73 has the unusual property that decrypting a ciphertext block consisting entirely of zeros gives a plaintext block consisting of eight repetitions of the same byte (0x87).

How was this key originally found?


texts: In the Quadratic Sieve, why restrict the factor base?

texts:
In the Quadratic Sieve, when factoring a number $N$, many descriptions and most implementations select as the factor base the set of small primes $p_j$ less than some bound $B$ restricted to having Legendre symbol $\left({N\over p_j}\right)=+1$.

Why this restriction of the factor base to primes $p_j$ such that $N$ is a quadratic residue modulo $p_j$? I wonder, because:

Wikipedia's introductory description of the Quadratic Sieve does not use such restriction, and works; the restriction is introduced in an example, without justification (in the article as it stands now).
Such restriction considerably lowers the density of integers having all factors in the factor base, arguably making it harder to find $x$ such that  $x^2\bmod N$ has all factors in the factor base (or more generally to find $(x,k)$ with $x^2-k\cdot N$ smooth).
A find including a factor not matching the restriction can help a successful factorization; borrowing the example in Introduction to Mathematical Cryptography section 3.6, trying to factor $N=9788111$ (by sieving $x^2\bmod N$ for $x$ starting at $\lceil\sqrt N\rceil$, by the same algorithm as in Wikipedia), it is found 20 smooths values of $x^2\bmod N$ for $x>\sqrt N$ among which it is selected (by Gaussian elimination)
$$\begin{align}
3129^2\bmod N&=2\cdot5\cdot11\cdot23\\
3313^2\bmod N&=2\cdot7^2\cdot17\cdot23\cdot31\\
3449^2\bmod N&=2\cdot5\cdot7^2\cdot11\cdot17\cdot23\\
4426^2\bmod N&=2\cdot3\cdot47^2\\
4651^2\bmod N&=3\cdot23\cdot31^3
\end{align}$$
where the last two relations would have been eliminated by the restriction of the factor base, since $\left({N\over 3}\right)=-1$; however, by taking the product of these relations, it is found that
$$(3129\cdot3313\cdot3449\cdot4426\cdot4651)^2-(2^2\cdot3\cdot5\cdot7^2\cdot11\cdot17\cdot23^2\cdot31^2\cdot47)^2$$
is a multiple of $N$, from it is found $2741$, a nontrivial factor of $N$, by computing
$$\gcd(N,3129\cdot3313\cdot3449\cdot4426\cdot4651-2^2\cdot3\cdot5\cdot7^2\cdot11\cdot17\cdot23^2\cdot31^2\cdot47)$$

Note: For the purpose of the question, please disregard the improvements of including $-1$ in the factor base; or/and allowing use of one or a few primes larger than the bound $B$; or/and (unless relevant) electing to factor $m\cdot N$ for a small multiplier $m$.


texts: Brute force knowing a part of the password

texts:
So here is the problem, my brother forgot about the eight digit numeric part of his password, he is using Ubuntu 15.04 default whole disk encryption

To make it clear, this was his password (example)

  thiswashispassword12345678

He completely forgot about the 12345678 part, to make things worse it was his working laptop with lot of important documents in it, for "backup" he was using raid 1 so same problem, his boss gave him a month top to recover the data or he is fired, is he screwed?


texts: Why is a simple hash into $G_2$ for (certain) pairing based crypto not possible?

texts:
In the paper Pairings for Cryptographers we read about what the authors call a type 2 pairing in which we have a "pairing friendly curve $E$ over $\mathbb{F}_q$ with embedding degree $k>1$ and define $G_1$ to be the subgroup of $E(\mathbb{F}_q)$ of order $l$". We also define $G_2=\langle Q\rangle$ where $Q\in E(\mathbb{F}_{q^k})[l]$. In this type of pairing we have a group homomorphism from $G_2$ to $G_1$.

The authors go on to say

  The advantage of the Type 2 setting is that we can use any curve and still get a homomorphism from $G_2$ to $G_1$. The disadvantage is that the group $G_2$ has no special structure. It seems to be impossible to sample randomly from $G_2$ except by computing multiples of the generator $Q$, hence we cannot securely hash to $G_2$.

Why is computing multiples of the generator $Q$ not a secure way to hash into $G_2$? For instance, say the order of $G_2$ is larger than $2^{256}$. Why couldn't I use a 256 bit hash function $h$ to help hash into $G_2$? Specifically my hash $H:M\to G_2$ where $M$ is the plaintext space would be something like $H(m)=h(m)Q$.


texts: Is a digital signature of use if you don't also encrypt the message containing it?

texts:
I'm sure this has been asked before. Its just too blindingly obvious.

from wikipedia

"Digital signatures, in which a message is signed with the sender's private key and can be verified by anyone who has access to the sender's public key."

So lets say Bob sends Alice an unencrypted message, and Charlie overhears it. What's to stop Charlie from signing his own messages with that private key and  henceforth having the ability to impersonate Bob?

So is there a point to digitally signing some message that isn't also encrypted? Or are all communications using digital signatures also encrypted? Wikipedia made it seem like there were two independent ideas, but I can't see a use case for signing-without-encrypting, where I can for encrypting-without-signing and encrypting-and-signing.


texts: How difficult is inverting a non-square matrix?

texts:
Partially inspired by ring learning with errors (RLWE), I am trying to construct a cryptosystem that requires the use of a non-invertible matrix.

Of the methods I've thought of to generate a matrix of determinant $0$, erasing a row/column or two seems the easiest, but I have no idea on how non-invertible this is.

I would like to know about known methods of reconstructing an unknown square matrix with known structure from its product with a non-square matrix.


texts: FHE - Brakerski's "Scale Invariant" Scheme

texts:
I thought the current state of the art for fully homomorphic encryption was Brakerski, Gentry and Vaikuntanathan's scheme (BGV) based on standard/ring LWE employing modulus switching for noise management.

I recently came across a paper by Zvika Brakerski on a "scale invariant" FHE scheme, based on gapSVP, that does not require modulus switching.

Is there an opinion on whether the latter "scale invariant" scheme (I haven't fully read the paper as yet) represents the current state of the art in the FHE world?


texts: Measure Strength of Mix Mode Modular Arithmetic based Confusion Layer

texts: Strength of sboxes is generally measured by different properties eg non linearity, fixed points etc. If confusion is provided by Mixed Mode Modular Arithmetic (eg as in IDEA), how to measure the strength of this type of confusion layer? Also, my sample mixed mode modular arithmetic based confusion layer takes 64 bits input and generates 64 bit output.


texts: Is there a cryptographic way (a la mental poker) two people can determine if they both Like each other, without revealing their personal preferences?

texts:
Specifically: Alice and Bob want to know if they like each other, but won't admit it if the other person doesn't reciprocate. (They're teenagers, or physicists.) They don't trust anyone else, so want to do it cryptographically.

So, say A->B=1 if Alice likes Bob, 0 otherwise. And let B->A=1 if Bob likes Alice, and zero otherwise. They want to compute "(A->B) AND (B->A)", without revealing their individual rankings. Is there a way that the following sequence could be applied:

Alice encodes her answer (either flipping her bit, or not) and sends it to Bob
Bob applies some function to Alice's preference and his own, and sends the answer back to Alice (but also possibly sends some other information or output from the calculation)
Alice applies some inverse function to determine only whether both A->B and B->A were 1, and announces the outcome, without her being able to know (or determine) B->A (excluding repeated games, or Princess Bride style psychological arguments).

My gut instinct is that this can't be done (the AND operator destroys information, and providing any extra outputs would allow Alice to determine Bob's true feelings) but intuition is hard. I'm thinking of solutions along the lines of  poker by phone and the Three-Pass Protocol. It's similar but different to Yao's millionaire problem, which allows two parties to secretly decide if a>=b; that's not sufficient in this case (both because it doesn't distinguish between (1,1) and (0,0), and because it could allow them to quickly deduce their opposite's opinions.

More generally, it could apply to any situation where revealing the truth would be problematic unless the other person was on board.

Appreciate any thoughts!


texts: What is algorithm of ECDSA multisignature?

texts: ECDSA signing/verifying with one signature is explained in Wikipedia and nayuki library whereas I search algorithm for signing by more than one party. For Bitcoin, for example, is possibility 1-of-2, 2-of-2, 2-of-3 etc. How do it?


texts: When using Curve25519, why does the private key always have a fixed bit at 2^254?

texts:
When using Curve25519, the private key always seems to have a fixed bit set at position $2^{254}$.

Why is that? Is there any good reason to use a fixed positioned most-significant-bit in the private key?


texts: Standard format to encode AES cipher and random IV

texts:
As far as I understood, a secret key (same length as CBC block size) and an initialization vector (IV) are needed to decrypt a AES-256-CBC encrypted string. As the IV should better be random, it has be distributed in plaintext along with the encrypted text.

Is there a standard or at least "commonly used" format to format the result?

E.g. /usr/bin/openssl seems to concatenate "Salted___" + IV + cyphertext and then base64 encode everything. Would this be a recommended way? I want to store the encrypted text and still be able to decrypt it in 10 years with any PHP/Python/Java library.


texts:
For a login the user credentials are typically some form of "username" and a matching "password".

The password is (hopefully) stored as a hash in the database.

But what about the username?

Is the username stored as a plaintext in the database?

Would it be a good idea to hash both the username and the password?


texts: standard way to authenticate parties with public keys without certificates

texts:
Is there some standard protocol for mutual authentication of two parties when there is possibility to use public key cryptography? The problem is that two parties can use public key cryptography but public keys are not embedded within any kind of certificates. Is there a way to avoid MITM attacks? Simple use of public keys for authentication does not solve the problem of MITM attack (I would have to be sure about public key authenticity first). If I understand correctly FIPS 196 requires usage of authenticated keys so this is no solution.
Is it possible? If there is no previous communication and no certificates then how would it be possible for Alice and Bob to recognize that there is Eve trying to do something nasty?
And if there would be possibility for Alice to verify the fingerprint of Bob's public key that would be possible? Is there some standard protocol for this?


texts: Figuring out key in hill cipher (chosen-plaintext attack)

texts:
I have been wondering what approach to take in order to figure out what key was used to encrypt a message using the hill cipher.
I know it is possible to obtain it even if it were just a known-plaintext attack, so it should be fairly possible for a chosen-plaintext one.
I'm trying to figure it out with just intuition, but since I know freq. analysis won't be of help, I don't know what else to try. I want to get my head around this, but could someone point me in the right direction?


texts: What are the "natural language input messages" that were used to derive Streebog's constants?

texts:
This is more "cryptography trivia" than proper cryptography, but I'm curious. In Note on Streebog constants origin, V. Rudskoy says that the constants used in the definition of the Streebog hash were derived by taking a "Streebog-like hash function" (defined in the note), and running it on "12 different natural language input messages".

These 12 messages are given in a table, but only as opaque hexadecimal strings that are presumably some kind of encoded Russian text (maybe cp1251?). What is the encoding, and what do the texts mean, for those of us who don't read Cyrillic or speak Russian?


texts: How does the challenger choose the message randomly in the one-wayness security game of PKE?

texts:
I have read some papers that give the definition of one-wayness of PKE schemes.

Let $\Pi = (G,E,D)$ be a PKE scheme, and the security game of OW-CPA is defined as follow:

$$\mathrm{Adv}_{\Pi,\mathcal{A}}^{\text{ow-cpa}}(k) = \Pr\left[ m = m' \left\vert
\begin{gathered}
(pk,sk) \gets G(1^k) \\
m \gets \mathcal{M}_{k} \\
c \gets E_{pk}(m) \\
m' \gets \mathcal{A}(pk,c) \\
\end{gathered}\right.\right]$$

We say $\Pi$ is secure in the sense of OW-CPA if $\mathrm{Adv}_{\Pi,\mathcal{A}}^{\text{ow-cpa}}(\cdot)$ is nelgibile.

My question is that how does the challenger choose $m$ over $\mathcal{M}_{k}$ randomly? Is $m$ an element picked uniformly from $M_{k}$?

If $\mathcal{M}_{k} = \mathcal{M} = \{0,1\}^*$, $m$ cannot be picked uniformly from $M_{k}$.

If $|\mathcal{M}_{k}| = \mathrm{poly}(k)$, then $\Pi$ cannot be secure in the sense of OW-CPA if $\mathcal{D}_{k}$ is uniform.

Let $F$ be the sample circuit, then
$$\mathrm{Adv}_{\Pi,\mathcal{A}}^{\text{ow-cpa}}(k) = \Pr\left[ m = m' \left\vert
\begin{gathered}
(pk,sk) \gets G(1^k) \\
m \gets F(\mathcal{M}_{k}) \\
c \gets E_{pk}(m) \\
m' \gets \mathcal{A}(pk,c) \\
\end{gathered}\right.\right]$$

Assume that the distribution of message is $\mathcal{D}_{k}$, thus $m$ follows $\mathcal{D}_{k}$. We cannot define that $\Pi$ is OW-CPA secure if for every distribution $\mathcal{D}_{k}$, $\mathrm{Adv}_{\Pi,\mathcal{A}}^{\text{ow-cpa}}(\cdot)$ is negligible, because it is not OW-CPA secure if $\mathcal{D}_{k}$ is a one-point distribution.

Perhaps, we may define the PKE scheme as $\Pi = (G,E,D,F)$ where the sample circuit $F$ is given at first. But the notion of IND-CPA or SS-CPA does not need $F$.

[FO99] Secure Integration of Asymmetric and Symmetric Encryption Schemes

[BF03] Identity-Based Encryption from the WeilPairing

[GH05] Security Notions for Identity Based Encryption


texts: Shouldn't a signature using ECDSA be exactly 96 bytes, not 102 or 103?

texts:
Attempting to use openssl to create a signature is confusing on several levels:

If I'm using it to sign a hash that I've already created (HMAC-SHA-384-192, specifically),

a. why must I specify another hash algorithm?

b. What algorithm is consistent with the one in the HMAC and ECDSA-384?
Why does the signature size vary between 102 and 103, instead of being exactly 96?
If I'm supposed to append a binary signature onto a potentially binary message (UDP), how is the recipient going to figure out where a message of unspecified length ends and a signed digest of unspecified length begins?


texts: Is the following authentication protocol insecure?

texts:
I am a student taking cryptography this semester. I was just wondering why can't we use this simple protocol?

Alice → Open Connection → Bob
Alice ← Cert$_b$ ← Bob
Alice → {K$_{AB}$}$_{Bob}$ → Bob

Assume bob is the server and we're only interested in one way authentication.
Is there anything wrong with it in terms of security and performance?


texts:
As I am reading the Paper: MDx-MAC and building fast MACs from hash
functions

I am having trouble understanding the Attack on the Envelope Method (4.3). In particular, I am not sure what chaining variables are referring to and what Prerequisites have to be met in order to execute the attack.

Maybe a more detailed/ rephrased explanation could help me to understand the gist of the attack.


texts: Increasing the diffusion of the AES-CBC encryption algorithm in pycrypto for python

texts:
When encryption is done using the AES-CBC algorithm, the encryption can be thought of as chaining the cipher texts with the previous ones and an IV. However, if its on CBC mode, we give our cipher text forward diffusive properties (i.e. if we change but i in our cipher, plaintext is change for all blocks after that). To make malleability attacks harder, one can chain the cipher texts during encryption on both directions (or implement something similar as in the bitLocker paper).

Does anyone know if there a implementation of pyCrypto that provides a chaining of the cipher texts using both direction?

One way that I thought of solving this was getting the original cipher text, reversing it using python and then feed it to pyCrypto. However, this seemed a little brute force because the whole point of pyCrypto is to take advantage of their C level implementation (while reversing a string would introduce a obvious unfortunate performance hit).


texts: What motivated the creation of RSA and ECDH?

texts:
Recently I've been learning about cryptography and so far I am loving it. However, there are some things I do not comprehend.

As far as I know, RSA was published in 1979 while New Directions on Cryptography by Diffie and Hellman was published in 1976. What I wonder is, what motivated the creation of RSA? Was it because they wanted to create something more secure than Diffie-Hellman? And if so, why is it more secure? Or was it because it was designed for other purposes which couldn't be accomplished with Diffie-Hellman?

On the other hand, it was not until 1985 that Neal Koblitz proposed cryptography based on elliptic curves. I've been told that elliptic curves offer more security than classic Diffie-Hellman but I'd like to understand and know how. I don't know much about security level. I've seen expressions like "$n$-bit keys give $m$-bit security" but I do not fully understand what do they mean. I see that ECDH offers more bit security than DH, but how can that be measured if attacks for both are not the same?

Thank you! And don't worry about throwing some math, I will probably understand.


texts: The GCD strikes back to RSA in 2019 - Good randomness is the only solution?

texts:
When someone collects lots of RSA public modulus, the first thing that comes to mind is;
$$\text{GCD them all}$$
If you calculate the GCD of two different RSA modulus and if the result is not 1 then you find one of the factors. This has been actively studied in

2012 - Heninger et. al Mining your Ps and Qs: Detection of Widespread Weak Keys in Network Devices

These researchers collected 5.8 million unique TLS certificates and 6.2 million unique SSH host keys. In the combined collection, there were 11 million distinct RSA moduli and they were able to factor 16,717 distinct public keys. I.e. breaking 23,576 (.4%) of their TLS certificates and 1,013 (.02%) of the RSA SSH host keys.

2012 - Lenstra et. al Ron was wrong, Whit is right

They collected 6.2 million digital certificates across the Internet they found that approximately 4.3% of these certificates fully share their RSA modulus with another.

2013 Bernstein et. al, Factoring RSA keys from certified smart cards: Coppersmith in the wild

The researchers investigate Taiwan’s national “Citizen Digital Certificate” database that contains more than two million RSA modulus. They have efficiently factored 184 distinct RSA keys. They are noticed that some of the primes occur more than was like p110 occurs 46-times. The reason was the flawed random-number generators in some of the smart cards.

2016 - Hasting et.al, Weak keys remain widespread in network devices

To see the response of the vendors and end-users, the authors examined 81 million distinct RSA keys and were able to factor 313,000 keys (.37%). They see that a significant number of new devices from Huawei, D-Link, and ADTRAN was vulnerable.

2016 Barbulescu at. al RSA Weak Public Keys available on the Internet

They crawled GitHub SSH-RSA keys between 22 December 2015 and 7 January 2016. They were only factor 1 with 512-bit. They also analyzed a ransomware database that contains 2048-bit RSA that contains none weakness.
From raw X.509 certificates collected during 2012, they tested 26177420 1024 bit RSA keys tested, 63502 (0.25%) keys were found to be factorized.

2018 - N. Amiet and Y. Romailler, researchers from Kudelski, Reaping and breaking keys at scale: when crypto meets big data.

They collected 340M RSA keys and 210k are broken. 1 key out of 1600 is vulnerable to batch-gcd by written by Chapel.
And recently;

2019 - Researchers at KeyFactor Factoring RSA Keys in the IoT Era

They scraped 75 million RSA certificates from the Internet between 2015 and 2017, a total of 250,000 could be completely broken. That is 1 in 172 shares a factor.
One solution to prevent the common factor is a public database. That is downloadable so that one can test their new modulus with the GCD. Of course, such a database has another issue. The reason that causes the same prime generation, the randomness process, can be exploited by some attackers. In any case, the attackers can scrape their database as researchers.
Questions:

Can A good random number generator solve this issue if we consider we are using RSA-2048 and let say we need 1 billion RSA modulus?

What is the probability that we can select a prime at least twice if we only consider 1024-bit numbers?

Why don't we generate the primes in different bit domains like 1024,1025,1026,1027-bit,...


texts: What does “simulator” and “interactive” mean in a cryptographic credential system's definition of security?

texts:
Definition 1 on Page 7 of “An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation” by Camenisch and Lysyanskaya, uses the term “simulator” in defining the security of a cryptographic credential system, which I'm finding a little confusing.

In particular, the sentence says:

  CSS is secure if there exists a simulator S (ideal-world adversary [defined above as a probabilistic polynomial time machine]) such that the following holds: […]

What does “simulator” in a cryptographic credential system's definition of security?
Also, what does it mean for a probabilistic machine to be "interactive"?


texts: What does this Authentication protocol achieve and what information is shared?

texts:
I'm having trouble with the following question from my class:

  "What is the purpose of the protocol, and how does it achieve this purpose and what shared information does A and B end up after running an instance of this protocol?

  $\sf A \to B: \quad A, N_A$
  $\sf B \to S: \quad B, \{A, N_A, T_B\} K_{BS}, N_B$
  $\sf S \to A: \quad \{B, N_A, K_{AB}, T_B\} K_{AS}, \{A, K_{AB}, T_B\} K_{BS}, N_B$
  $\sf A \to B: \quad \{A, K_{AB}, T_B\} K_{BS}, \{N_B\} K_{AB}$"

If anyone can help at all, I would greatly appreciate someone going through this question with me. It's not homework, it's not coursework. It's off a previous sheet of in class exercises that my teacher wouldn't go through with me.

I understand basic primitives, but I don't feel confident in my ability to look at an entire protocol and analyze its security properties.

See also How to attack this authentication protocol from "Cryptography: An introduction" for a more specific question about the same cryptographic protocol.


texts: Sensitivity of probability measure in differential privacy

texts:
I know that we need some sort of sensitivity(global, local) to calculate noise that needs to be added for differential privacy. The noise is the maximum difference between two neighboring datasets. However, if I am working in probability spaces, i.e. my values are bounded by 0,1. My sensitivity would be 1, which seems too large for adding noise to the probabilities.

I tried looking up any relevant literature that provides any tighter upper bounds, but no success. I am only interested in adding noise to the probabilities, not to the mechanism that they are generated from.


texts: Why do authors execute a leakage resilient election protocol inside a leak-free phase?

texts:
In the paper "Multiparty Computation Secure Against
Continual Memory Leakage", on page 1241 (that's page 7 of the PDF) under section 2.3, the authors discuss "The Election Protocol" that they use to elect committees.  The election protocol they use guarantees a constant fraction of honest parties and that each committee holds roughly the same number of parties.

In the same paper on page 1249 (that's page 15 of the PDF), you see the pre-proc phase is boxed in with 4 steps. The first step happens to be the execution of the election protocol.  Why does it have to execute inside the pre-proc box if the election protocol is leakage-resilient? The sole purpose of pre-proc box is to assume a leak-free environment. However, if the election protocol is leakage resilient… why on earth would the authors stick it in the pre-proc box?

This is baffling me. If I would have written the paper, I would have moved the election out of the pre-proc box before pre-proc even starts.


texts: Security of secure two-party computation with a trusted dealer during offline phase?

texts:
In the SecureML paper, one can assume that two non-colluding servers can run secure two-party computation protocol based on secret sharing with the help of a third party (client).
The client would send correlated randomness to the servers in offline phase, which can accelerate the computation in online phase, e.g. multiplication using Beaver's multiplication triplet.
I'm wondering how the security of this type of secure two-party computation is defined.
Is it secure if one of the servers and client collude?
Since the client knows the information about all the correlated randomness, does it incur some security flaw if that happens?


texts: Can an observer deduce a pre-shared key used multiple times on (nearly) random messages?

texts:
Imagine you took a standard one-way hashing algorithm (like SHA-256), and you implement it in hardware using simple logic gates.
Now, replace each logic gate with an equivalent reversible logic gate (e.g. toffoli gates).
Let's assume we're limiting our messages to 256 bits. We wind up with a circuit that produces the usual 256 bits of the SHA-256 hash, plus an additional 256 very large number of output bits representing the captured entropy of the circuit.
Together, these two sequences of bits can be used to reconstruct the original message (by running an instance of our hardware in reverse), but the actual result is essentially random (or as close to random as you can get with a deterministic hash function).
$$(x,h) \leftarrow \operatorname{Tuffoli-SHA256}(m)$$ where $m$ is the message, $h$ is the result of $h = \operatorname{SHA256}(m)$ and $x$ is the Tuffoli gate information.
Suppose you then have a sequence of messages you want to send securely. You and your friend have a pre-shared key $PSK$ consisting of random bytes, with the same length as $x$ appended to $h$, $h\mathbin\|x$.
For each $m_i$, you generate what you now hope is a private message $p_i$:
$$p_i = PSK \oplus (h_i\mathbin\|x_i)$$
(Where $\oplus$ is XOR.)
The idea I'm getting at here is that even though ($h_i \mathbin\| x_i$) contains all the information necessary to reconstruct $m_i$, it looks like random noise.
My understanding is that if you re-use a random key this way on natural language text, you're vulnerable to crib-dragging attacks.
The difference here is that each $p_i$ itself is appears to be random noise, so it shouldn't be vulnerable to crib-dragging.
So the question is: are there other attacks that could be used to deduce $PSK$ from a sequence $p_n \ldots p_{n+k}$ observed on the open channel?


texts: I need to implement the HASH algorithm (MD5 & SHA-1) on an 8 bit MCU. I hear it can only be implemented on 32bit and sometimes 16bits MCU. Is that possible? I will appreciate link where possible. A program in C language most preferred.


texts:
Are there dedicated protocols to achieve a private set intersection where one of the set is of small constant size $c$ and the other one of size $n$?

What are the resource complexities of this kind of protocol, in terms of communication and computation?


texts: Why doesn't this dummy mutual authentication protocol provide mutual authentication?

texts:
I am a student taking a cryptography course so forgive me if this comes off as a silly question.
This is an assignment question:

  $Alice \rightarrow R \rightarrow Bob$
  $Alice \leftarrow [R]B \leftarrow Bob$
  $Alice \rightarrow [R+1]A \rightarrow Bob$

  Why doesn't this protocol provide mutual authentication?

Here's a plausible scenario:

Alice sends $R$. Trudy intercepts it and sends it to Bob impersonating Alice. Bob sends back $R$ signed by him to Trudy. Trudy now impersonates Bob and sends $R$ with Bob's signature to Alice impersonating Bob. Alice sends $[R+1]$ signed by Alice which Trudy can now use to impersonate as Alice to Bob.

If that is a valid attack. Wouldn't this work with every protocol? After all we're merely just relaying message back and forth among the two parties.


texts: Why we use Mix Columns and Shift Rows in AES? FOr example, if i want implement an AES algorithm without Mix Columns and Shift Rows what is the difference in the ciphertext?


texts: Is it feasible to build an index of prime factors?

texts:
Would it be possible to break an RSA key, in for example 1 week of time, if the cracker have already spent X number of years building an index of primes by performing every permutation of existing prime keys up to $2^{2048}$?

I understand this would take an immense amount of time to do, but it would only be done once. Obviously, computing such an index would take a considerable amount of time and would have to be done with someone having the right amount of resource. Given the public key, you would be able to look up what the two primes are, and hence retrieve the private key instantly.

Breaking an 256 AES would then be easier, as AES keys are often generated using the RSA private key.

Would it be possible to build such an index? How long would that take in permutations and perhaps with the fastest computer in the world?


texts: Parallelization of CFB mode encryption and decryption

texts:
While reading Evaluation of Some Blockcipher Modes of Operation by Rogaway (someone just linked it somewhere), I noticed two claims about CFB that I'm not sure I understand:

Regarding whether CFB mode encryption is parallelizable the paper says (on page  31):

  Yes, but awkward. See ISO 10116 for less awkward generalization.

Regarding whether the decryption is parallelizable it says (same page):

  Yes, but awkward.

I can't see how this is true at all. To encrypt a block with CFB mode you need the ciphertext of the previous block (or more if $s < n$), so how can you parallelize it?
Parallelizing the decryption algorithm, OTOH, seems very simple, especially when $s = n$ (which I suppose is the "common" case?). I'm unsure what is supposed to be awkward about it, unless it's the fact that with $s < n$ you need to look back more than one $s$-bit block of ciphertext? But since you are still just taking the previous $n$ bits of ciphertext, this seems just like CBC, which wasn't considered awkward.

The ISO 10116 reference might be helpful for showing which awkwardness it avoids, but I don't have access to it.


texts: Advantage of Asmuth-Bloom secret sharing scheme with polynomial over integers?

texts:
Currently, I am studying the Asmuth-Bloom secret sharing scheme and want to learn more about its polynomial version.

What are the exact reasons to use polynomials over integers for this scheme?


texts: Does XEX mode specify how the whitening value is generated?

texts:
When the term "XEX" or the phrase "XOR-encrypt-XOR" is used, does it refer only to the scheme $CT = E_{K}(PT \oplus T) \oplus T$/$PT = E_{K}(CT \oplus T) \oplus T$ (where $T$ is the whitening/tweak value), leaving out how the value of $T$ is changed between blocks if it is even specified to be changed at all? Or does it also refer to a specific method of changing $T$ between blocks?

If it is the former, then does that mean the birthday bound will apply to any mode of operation constructed around it where $T$ is deterministically generated? For instance, let's say we use the second method of generating the tweak as specified in this question where $T = E_K(IV \boxplus i)$. What would happen if this were used to encrypt more than $2^{0.5 \times n}$ blocks?

If it is the latter, then does the birthday bound only apply to when $T$ is stepped using finite field multiplication as in XTS?


texts: Can I do a forward secure half-round ephemeral-static ECDH?

texts:
In the context of the project we are working on recently, we would like to enable users to "leave a message" to someone on the Internet securely. Our setting is as below:

ECC key pairs for open ID
AES-GCM as session for each message
Suppose Bob wants to leave a secret message to Alice, whose public key is known to the public.

Alice's key pair is (priv_a, pub_a)
Bob's key pair is (priv_b, pub_b)
Bob generates an ephemeral ECC key pair (epriv_b, epub_b)
Bob computes the shared secret of epriv_b and pub_a
Bob derives an AES-GCM key from the shared secret and creates (epub_b, sig of epub_b using priv_b, encrypted message using AES-GCM key) as M
Bob leaves this message somewhere (could either be public or private) so that Alice could see it
Alice performs the same process to derive the AES-GCM key to decrypt the message and verify Bob

In this scenario, the forward secrecy is not guaranteed. I am curious if we can possibly ensure the forward secrecy under this scenario with only half round of communication (one-sided). If not, is there any alternative that I can adopt to accomplish the goal? Any direction or hint is appreciated.


texts: I was wondering whether there exists randomizable zero-knowledge proofs. What I mean by randomizable is that assume I have a zero-knowledge proof of knowledge $\pi$, stating that I know $x \in \mathbb{Z}_q$ for a prime $q$, such that $Q = g^x$, and I randomize $Q$ as $Q' = Q^r$ for a random $r \in \mathbb{Z}_q$. Then, I wish to prove that $Q'$ is a randomized version of $Q$. So, is it possible to somehow also randomize the proof $\pi$ into $\pi'$ for this?


texts: Is HMAC-MD5 collision-resistant if the key is unknown?

texts:
I'm in a situation where I need to use HMAC-MD5 (for a learning, non-production application) and it needs to be collision-resistant.

So my question: Is HMAC-MD5 collision-resistant if the key is unknown, ie you are only given standard oracle access to an HMAC-MD5 oracle?

Alternatively, if possible you can replace "MD5" with "any Merkle-Damgård hash function for which collisions are known" (which is a more general statement).

Note that "Is HMAC-MD5 still secure for commitment or other common uses?", while related, only talks about the situation with a known key to the adversary.


texts: Comparing stronger vs. weaker assumptions

texts:
If I have to argue that an assumption A is stronger than B, should I argue this way:-

An adversary breaking the security of A does not translate to breaking the security of B. But, if an adversary breaks the security of B, it can break A too.

Right? or, there are other ways to compare stonger vs. weaker assumptions.


texts: How to formally prove that a given hash construction is collision resistant or not?

texts:
Is there a precise procedure or strategy to follow in order to prove in a formal way the (not) collision-resistance of a certain given hash construction? I.e. let $H_1$ and $H_2$ be two hash functions, then define the following construction $H(x) = H_1(x)||H_2(x)$. How could one formally prove that such construction does not yield any collision, given that at least one of $H_1$ and $H_2$ is collision resistant?
I know, in this case, the concatenation of a sequence of hash functions is collision resistant if at least one of the hash functions in the sequence is collision resistant. But, my question here is if there's any formal way of proving it.


texts: Can Fully Homomorphic Encryption do comparisons?

texts:
I encountered a simple function that even FHE cannot solve. Here's it:

int f(a,b,c,d){
   if(a+b>c+d) return a+c;
      else return b+d;
}

Since FHE is not order-preserving, one can't figure out whether a+b>c+d without the decryption key. That means even if practical FHE was implemented, f(a,b,c,d) cannot be computed in the Cloud independantly and securely. Not to mention linear regression, or more complex functions.

So I wonder with such an obvious limitation, why is FHE called "the holy grail of cryptography"?


texts: How to compute the inner product on encrypted vector by using a third party?

texts:
I want to compute the inner product of two vectors on a third party, i.e.
$f(x) \cdot f(y) = x \cdot y$
where $x$ and $y$ are two vectors. However, I do not want the third party knows the real value of the two vectors.

So is there any encryption scheme that can do this?


texts: How to select elements randomly from a multiplicative group Zn*

texts:
I am working on a problem in which I have two large safe primes say p and q randomly selected each of 512 bits. I have generated these safe primes using OpenSSL library.Now,

  n = pq

What will be Zn* called? Is it a group under multiplication modulo n and same as (Z/nZ)*? But I have read that (Zn,⋅), integers modulo n under multiplication, is a group if and only if n is prime?
In this link

What all comprises the elements of this group if at all this is a group? And is there way to select its elements randomly using a code in C/C++ using some library like Openssl.

Thanks and Regards.


texts: How should I manage Diffie-Hellman parameters on a Web Server?

texts:
Is there a best practice for Diffie-Hellman parameters (p, g, and q) used on a web server?

The server is using ephemeral keys, but should the parameters be rotated on a regular basis? Is it OK for the server to keep them fixed for years (in the source code)? Or should they be generated uniquely for each site?

This server does not appear to be under NIST and FIPS, so I don't believe they need to be fixed for compliance.


texts: MD5: Existence of invariant (fixed point)

texts:
Is it possible to find 128 bits $B$ such that $md5(B) = B$?

md5 has collisions that can be computed in acceptable time, but I did not find any papers on fixed points in md5.

As pointed out in this question from 2014, there is a 63.2% probability for a totally random hash function to have a fixed point. Since some time has passed, I would be interested in newer research into the topic of fixed points, even if the analysed algorithm is not md5 itself.


texts: Do quantum computers  have any affect on the ability to solve the non-linear AES s-box algebraic expression, or does solving it still fall under search algorithms (Grover's)? If quantum computer do help solve it, what affect does this have on AES given that finding the key is still a brute-force search?


texts: Does the Blake3 hash have identities, due to its merkle tree structure?

texts:
I've read that the Blake3 hash uses a Merkle Tree.
Does it follow that there are identities such as:
b3sum("This is ") xor b3sum("a test.") == b3sum("This is a test.")

The example above does not work, perhaps because the block size is not eight bytes.
Are there any real Blake3 identities of a similar form?


texts: Why are multiple rounds with generated subkeys used?

texts:
In AES-128, 10 rounds are used with subkeys generated from the 128-bit key. In DES, 48-bit subkeys are generated from a 56-bit key. This seems to be common in symmetric encryption.

I ask this because of my understanding of entropy and randomness. If you were to take a random integer and put it through some function to expand it (the terminology used in the AES standard), aren't you making it more predictable/less random?

If I were to take a random integer and use it as the seed to a PRNG, I'm not getting anything unpredictable from the seed as I retrieve values from it. Surely the stream has the same randomness as the seed alone. I would have thought that it follows that multiple rounds result in encryption with multiple low quality subkeys with significantly less randomness than the original key, assuming the original key was random, or at least we don't know what it is.

(This PRNG and randomness analogy may be misinformed; I'm simply trying to say that you can't make an unpredictable value bigger and be as unpredictable as it was before, which is my understanding.)

Please could someone clarify why using multiple rounds of a lower quality subkey is more desirable than, say, one round with the whole key (in the case where key length is the block length)?


texts:
What is the proper/canonical way to do this?
For example, $0 < r1 < 1$ and $0 < r2 < 1$. Presuming uniformly distributed probabilities for the two, combining/averaging them is going to bias very quickly towards $0.5$.
The specific use case I have is a game/simulation I'm programming. An entity has a random number it was given that's specific to it; Their individual behaviours also have random numbers associated with them. For the purposes of most behavioural calculations, I only use the behaviour random number, but for a few I want to incorporate the entity's random number. Simply averaging them will result in less randomness.
Desired Outcome : Deterministically combine more than one source of entropy
So “Entity A” may have a small random number, and so most of its attributes are skewed small. It's behaviour random number happens to be big, so most of its behaviour attributes are skewed large. When combined the two random numbers deterministically result in $n$, and so some of its behaviour attributes skew towards $n$.
RE: Off-Topic
My question is not specific to game development. The particular use case is. How do cryptographers deterministically combine sources of entropy? I assume they have uses case for this outcome.


texts: Construct an encryption algorithm using hash function

texts:
We know that Cryptographic hash function is generally a one-way function where we can't retrieve the original message. On the other hand, encryption is a two-way-function where we get the original message from the encrypted message or vice versa. So, in a normal sense, we can't use hash function to construct an encryption algorithm.

What I want to know is, if it’s theoretically possible to somehow create an encryption algorithm using a hash function, or if any encryption algorithm uses hash function in any part of their algorithm?


texts: Suppose Alice and Bob both want to determine whether the other has a crush on him/her, but they only wish to share the information if the crush is mutual. Is there a cryptographic protocol that makes this possible without using trusted third parties? It is safe to assume that they will not lie during their "encrypted announcement" to the other.


texts: learning with errors is hard even when given some information about the secret vector

texts:
In this case we are given the distribution D from which secret s is sampled. If I can get some hints to proceed with the questions, it would be of help.

Thanks,


texts: Laplace Mechanism Proof: Why this product operator?

texts:
The equation below shows the proof of Laplace mechanism for differential privacy. I am not understanding the product operator, is this a common rule?

$$
\frac{p_x(z)}{p_y(z)} = \prod_{i=1}^{k}\left(\frac{exp(-\frac{\varepsilon |f(x)_i - z_i|}{\Delta})}{exp(-\frac{\varepsilon |f(y)_i - z_i|}{\Delta})}\right)
$$

While $p_x$ and $p_y$ denote the pdf of mechanisms $\mathcal{M}_L(x,f,\varepsilon)$ and $\mathcal{M}_L(y,f,\varepsilon)$ respectively. Important to notice that $x$ and $y$ are neighbor datasets. $x, y, z \in \mathbb{R}^k$

Thank you in advance.


texts: Can I use NaCl's scalar multiplication functions for Diffie Hellman Key Agreement?

texts:
I want to create some software that performs diffie hellman group key agreement but I don't want to reinvent the wheel even if I know how it's done. So I came accross the NaCl library, especially the scalar_mult functions.

As far I know you can perform Diffie Hellman key agreement on elliptic curves therefore, my thought is if I combine it with crypto_box ones for key generation, I can do a Diffie Hellman Key agreement.

My Idea is (described in some sort of pseudocode) shown in the following image:

Would you recommend it as shown above?


texts:
I have been reading a bit about how the Enigma machine was cracked in WW2.
There was also this wonderful post which highlighted a lot of useful information.
Let's assume I know everything about how the M3 Army Enigma machine works according to Kerckhoff's principle. Now I am wondering, in theory, if say, the Germans decided to design a new rotor, would it become obvious right away?
For example say I am attacking Enigma messages. Would I be able to immediately figure out (through analysis of encrypted messages) that "Oh they must have changed the rotor wiring! Send spies!!".
If so. The followup question is that, would I actually need to send spies in this case or could some sort of analysis be used to figure out the wiring of the new rotor?