texts:
In the context of cryptographic hash function collisions, what exactly is a pseudo-collision attack?

E.g., pseudo-collisions are discussed here:

Preimage and Pseudo-Collision Attacks on Step-Reduced SM3 Hash Function
Converting Meet-in-the-Middle Preimage
Attack into Pseudo Collision Attack:
Application to SHA-2

Also, is that term actually well-established and used consistently?


texts: TLS - self encrypting to avoid tls setup, secure?

texts:
I am in doubt : of course one can create a tl connection between a client and a server.

But what if the client sends self encrypted with, say, blowfish, data to the server? The goal is that the server remains dumb about tls.

The question is not if it is possible, it is.

But in case of a "unattended listening by someone who might love hats", would that be secure enough if the hacker gets the packet?

Would it lessen the security ?

To me, maybe yes, because the hacker would have the packet on his/her computer with the speed involved vs hacking a tls connection. But am I correct ?

Edit : I am new to the security context.


texts: How can two different passphrases unlock the same content?

texts:
I have heard that in enterprises it is common that the IT admin has a master passphrase that can unlock any content that an employee encrypts.

It would be temping to think, that the IT admin's passphrase is encrypted with the employees passphrase, but then the IT can't change his passphrase.

How does such encryption actually work?

Is there a cryptographic secure method of doing this?


texts: Why crypto hash functions must be collision resistant and how to find resistant?

texts:
Why cryptographic hash functions must be collision-free and is there any methods to evaluate whether a function is not resistant to collision?

Thanks,


texts: What are the minimum constraints on RSA parameters and why?

texts:
The RSA cryptosystem only works if certain constraints are applied to its input parameters. Some of those constraints are made to make it "hard" to determine the private key whereas other constraints are there to make the mathematics work. I want to understand the latter category of constraints and why they exist.
Here is what I have so far....

The public exponent $e$ and the modulus $n$ should be $e<\phi(n)$. It can be larger but there is no benefit because $e$ is congruent $\mod\phi(n)$.
There are no other restrictions on $n$ (the use of $n$ with prime factors $p$ and $q$ is just to make the problem "hard").
The public exponent $e$ must be $0<e<n$.
In practice and because of the above, $n>1$.
$e$ does not need to be prime but it should be coprime with $\phi(n)$ (see next point). It does not need to be coprime with $n$ but it doesn't matter if it is. It is usual for $e$ to be chosen from the Fermat Primes, usually $65537$ in real applications.
$e$ and $\phi(n)$ must be coprime to satisfy, for the private key $d$, that $ed\equiv 1\pmod{\phi(n)}$ if, by Euler's Totient Theorem and Bezout's Identity, $ed+k\phi(n)=1$ (where $k$ is a quotient of no relevance and can be any integer; $k$ and $d$ are computed from $e$ and $\phi(n)$ by the Extended Euclidean Algorithm).
The message $m$ (both the plaintext and the ciphertext) must be coprime with $n$ so that, by Euler's Totient Theorem, $m^{\phi(n)}\equiv 1\pmod n$. However, $m$ does not need to be coprime with $\phi(n)$ but it doesn't matter if it is.

I have read elsewhere that any $m$ should work, like this question explains, but that contradicts the last constraint and I've experienced that the algorithm somtimes fails without this.
I have a little program that evaluates the algorithm with some small numbers ($n$ < 20 bits). I find it breaks occasionally and, when it does, I find that $m$ and $n$ are not coprime.
I believe the minimum constraints are those that I've listed above. I'd like to understand whether I have it right or if I'm missing anything. If it should work for all $m$ there must be a reason why I find to the contrary.
Update
$m$ does not need to be coprime with $n$ but $gcd(m,n)$ must be coprime with $n/(gcd(m,n)$ but I don't understand why this is the case.
Optimisations can be performed if the factors, $p$ and $q$, of $n$ are known. They aren't necessary but can help improve decryption performance where $d$ is large. They are:

The reduced totient $\lambda(n)$, or Carmichael Function, can be used instead of Euler's Totient so, in the above, $\phi(n)$ can be replaced with $\lambda(p,q)$. This gives a smaller value for $d$ (and demonstrates that there are multiple $d$ values for a given $e$).

It's possible to use the Chinese Remainder Theorem (CRT) to break the ciphertext into two smaller parts so that two smaller exponents can be computed instead of one based on a large $d$. A good explanation of this technique is here.

When generating the private key, the CRT coefficients $dp$, $dq$ and $qinv$ (the inverse of $q\mod p$) can be precomputed and would form part of the private key. They are then used in decryption instead of $d$.
I don't understand why $\lambda(p,q)$ works and I've found that CRT only works when $p>2$ and $q>2$. The reason for this isn't clear but I think it is because a CRT coefficients when $p$ or $q$ is 2 will be taken modulo 1 which is always zero.


texts: Encrypt or decrypt using the private key, and decrypt using the public key?

texts:
I am currently trying to figure out if my following scheme is implementable in ECC or whether I can use existing implementation. At first I was going with libsodium but it seems that it really doesn't support my use case.

My scenario: There are basically two groups. Group A which has read access (only decryption) and Group B which has write/read access (both encryption/decryption).

libSodium has something which is very similar: crypto_box_seal/crypto_box_seal_open

The issue with libSodium's api is that crypto_box_seal_open requires both keypairs. I would need the reverse of this api.

eg.

private key => encryption/decryption
public key => decryption

Does a scheme like this exist?


texts: Is the IV value in Davies Meyer construction public?

texts:
I am learning the construction of Davies-Meyer to construct a hash function from block ciphers. The definition that I found is

$$H_i=E_{m_i}(H_{i-1})\oplus H_{i-1}.$$

where $E_k$ is a block cipher with key $k$.

My questions are:

1) Who is $H_0$, is the Initial Value (IV) as any hash function, that is Is that value public?

2) Suppose the follow case: the key size is 64 and the block size is 32, What happens if I need to evaluate the hash of the message $1$?

With respect to the question 2), I think that is necessary to complete with zeros until complete 64 bits the message $m_0 = 1$, then

$$H_1=E_{0000..00001}(IV)\oplus IV$$

but In this case it is easy to retrieve $m_0$ because the plaintext and the ciphertext are know. Where I am make mistake?

(See also Why are the Davies-Meyer and Miyaguchi-Preneel constructions secure? for a related question.)


texts:
I'm trying to setup an ECDSA math example using just integer math and multiply (no EC).  The purpose is just to help people understand why this works with out the added complication of understanding EC.  However, it looks like I either don't understand something or I'm making a simple math mistake.

Can someone help me fix this?

Here is what I'm doing:

Signer workflow:

private da = 7

G          = 2

pubkey     = da * G = 14

message z  = 10

n          = 17

k          = 13

k^-1       = 4

x1         = 26

r          = 26 mod 17 = 9

s          = 4(10 - 9 * 7) mod 17 = 8

Verify workflow:

w  = s^-1 = 15

u1 = z * w mod n = 14

u2 = r * w mod n = 16

x2 = u1*G + u2*pubkey = 252

r2 = x2 mod n = 14 <=== failed...??


texts: Converting normal alphabets to 64 bit plain text

texts: How can I convert a normal alphabetical text (say hi) to a 64 bit or 128 bit binary digit input for DES?


texts: Is parallel, vectorized NORX nearly as fast as hardware-accelerated AES-GCM?

texts:
As I understand it, NORX gets 3.5 CPB in an unoptimized implementation.

But NORX can be parallelized.  With 4-way SIMD, I would expect about 7/8 CPB performance.  This is nearly as good as AES-GCM in hardware.

Is something wrong with my assesment, or is parallel NORX a better choice in speed than ChaCha20-Poly1305?  Why were sequential versions the primary recommendations?

I also have the same questions w.r.t. Keyak, which has 1.8 CPB with 2-way parallelism and presumably 0.9 CPB with 4-way parallelism.


texts: Derive a key from a password and another key?

texts:
I would like to encrypt some data using a password. I want to use a function like PBKDF2 to turn my password into a key. However, I would like to also require a keyfile, for added security.  My data should only be decryptable if I have the password and the keyfile.

What is the "best" way to do this?

From what I understand, I should not be using the salt for this purpose, correct? I.e. I could use the salt as my "key file", and the password entered by the user as the password, but most literature I can find does not recommend using the salt this way.


texts: Post-Quantum cryptography usability in IoT devices

texts: My question is very simple. Can I use Post-Quantum encryption/decryption algorithms in IoT devices such as RaspberryPi, Arduino etc, or should the hardware infrastructure obey in quantum logic?


texts: Cryptographic algorithm for knowing who has more money?

texts:
I recall reading about this but forgot what it’s called.

Suppose two people want to know who is richer but don’t want to reveal their net worth to the other. How can they securely exchange info to determine who’s number is larger?


texts: Where is the OID and ASN.1 specified for AES_CMAC?

texts:
I have a requirement to implement AES_CMAC as the authentication algorithm in a CMS library.  I just can't seem to find the OID and the ASN.1 definition for it.

I expected to see the OID under {joint-iso-itu-t(2) country(16) us(840) organization(1) gov(101) csor(3) nistAlgorithm(4) aes(1)} since it appears to be a NIST Standard ( 800-38B )

Any help out there?  Thanks


texts: How to optimise a finite field multiplication?

texts:
I'm currently trying to optimise the finite field multiplication in $ \operatorname{GF}(2)[x]/(p)$, where $p = x^8 ⊕ x^7 ⊕ x^6 ⊕ x ⊕1 ∈ \operatorname{GF}(2)[x] $.

The thing is that I have to multiply by $ 16,32,133,148,192,194 \ \ and \ \ 251 $. Actually, what I do is that I declare 7 arrays (one for each multiplication; length 256) which contains every result. for example, when i want to multiply $ i = 145 $ by 32, i just assign $ array_{16}[i] $ to the result.

Is there an other way to do the multiplication, in order to reduce the memory used by my algorithm for example?


texts: XSLT tranform in xmlsignature form, a part of xmldocument?

texts:
I have a HTML page(A Form) where user will enter his details. Details to enter are NameagesalarystateCity Now when user enters all details and click Button then I will create xml file containing the user details like

<root>
<name>abc</name>
<age>40</age>
<salary>20000</age>
<state>xyz</state>
<city>abc</city>
</root>

After this I want to sign this xml file using XMLSignature. I want to sign only two elements of document i.e name and salary element using XSLT transform and some digest and signature method.

My question is how to use the XSLT transform in our xmlsignature's transform element. What is the best way to achieve this?

One more issue when the user presses Another Button in HTML page, He should be shown the elements which are signed i.e name and salary should be displayed to user. How can I achieve that. Will XSLT transform plays a role here also?

Note: I am using Java libraries for XMLSignature
Note 2: I have asked same question in stackoverflow site. Here is link https://stackoverflow.com/questions/10680590/xslt-tranform-in-xmlsignature-form-a-part-of-xmldocument. If i get answer i will remove that.


texts: How is it possible to define differential privacy on two databases that differ more than a single entry?

texts:
The original definition of $\epsilon-$differential privacy is for two databases $D_1$, $D_2$ that differ at most one entry and an randomized algorithm $A$.

We have a bound on the probability ratio
$\frac{Pr[A(D_1) \in S]}{Pr[A(D_2) \in S]} \leq e^\epsilon$ where $S$ is subset of range of $A$.

How do we define such thing for two databases that differ more than one entry?


texts: Supersingular vs non-singular (Same or different)

texts:
I have a frustration for the term "supersingular" elliptic curve and "non-singular" elliptic curve.

In some paper, performance evaluation is done using supersingular elliptic curve and in some cases, they use non-singular elliptic curve.
Are they same or different curves?


texts: Is it safe to use ECCSI-SAKKE as described on RFC6507-6508-6509?

texts:
In particular, is it safe to use them with the settings and the algorithms as they appear on the above RFCs?
I am confused in various ways … just an example.
In RFC6508 on page 3, the ‘E’ is defined as an elliptic curve ….. “ In this document, we use supersingular curves y^2=x^3 – 3 * x modulo p. “. However, in RFC6509 on page 5 section 2.1.1, I read “For MIKEY-SAKKE, the NIST P-256 elliptic curve … MUST be used”. …
Is the P-256 supersingular? … or what?
In general, what is your opinion of ECCSI-SAKKE?
Thank you very much for your answers.


texts: Is it possible to obtain AES-128 key from a known ciphertext-plaintext pair?

texts:
I have a file, which was encrypted with AES-128 in ECB mode. I know the format of the original file and know that all files in this format have the same headers. So, I have an encrypted block and the original block.

Can I get the encryption key, using this information?


texts: Simulator in Private Outsourced Computation over Outsourced Datasets

texts:
Please, consider two honest parties $A$ and $B$ outsourced their private data to a malicious server $S$. So the parties store their data in the server. Then at a later point in time they want to ask the server to run some computation on both parties data and return a private result back to a party.

In order to prove the security of the scheme,in the ideal world, we construct a simulator $SIM_s$ simulating malicious server, $A_s$.

Question: Does $SIM_s$, pick two random datasets, make them private and send to  $A_s$?

What is not clear in this case is that whether the parties (or simulator) have input or the server has input. Because the parties have already outsourced their dataset.


texts: Can the EdDSA signature scheme be customized with OpenSSL?

texts:
EdDSA has currently two signature schemes: Ed25519 and Ed448.

Ed25519 is the EdDSA signature scheme using SHA-512 (SHA-2) and Curve25519

Ed448 is the EdDSA signature scheme using SHAKE256 (SHA-3) and Curve448

Is it possible to use EdDSA with a custom algorithm (signature scheme) for instance a different curve and a different hashing algorithm like SHA-1?
Is this not possible because of an RFC standard?
Are there any cryptographic reasons why OpenSSL does not provide EdDSA that use other curves?
Does this have to do with OpenSSL not having the feature implemented?


texts: Distributing blocks with validation and non-dependant list generation

texts:
Problem
Suppose I have a system of nodes that can communicate with a parent node, but not among each other. Suppose then a file on the parent node is split up into blocks and divided among the children. The file is then deleted from the parent node.

If the parent were to then request the blocks back from the children, how can the original order be reconstructed without retaining a list of all the files on the parent. Additionally, to prevent one of the nodes from maliciously modifying a block, the parent would also have to validate the blocks coming back.

Optimal Solution
A system of naming the blocks of a file, where the list of files can be generated on any node given a seed. Given the list, a parent should be able to use the list somehow to validate the blocks coming back from children.

Attempt #1
So what I have got so far is the ability to minimally store a list of the blocks. I do so by naming the blocks as such:

block_0 = hash(file_contents)
block_n = hash(block_n-1) [hashing the name of the previous file]

This enables the order of the files to be retained by just keeping the seed (name of block_0), and the number of blocks (e.g. 5d41402abc4b2a76b9719d911017c592,5 --> seed,files). However this will not allow the files to be validated independently.

Attempt #2
Simply take the hash of each block and store that in a list. However this is not efficient and will result in a large amount of memory allocated to this task alone if a large number of blocks need to be tracked. This will not do.


texts:
Alice has a private key, $x$, and a public key $P = [x] \cdot G$ in a group of order $n$.

Alice would like to also publish her inverse public key (inverted modulo the group order) $P_{inv} = [x^{-1} \mod n] \cdot G  $, for the purposes of a simple homomorphic encryption algorithm that allows people to re-encrypt documents for her.  For simplicity, I'm going to assume that that system is otherwise perfectly secure.

Alice is using a pairing-based curve, and that same public key $P$ is used in a number of pairing operations, signing operations, and DH key exchanges that could be observed by an attacker.

Can this be used to make an attack on Alice's private key easier?  Now we have 2 equations - instead of one.

The closest related proof I've found is: Variations of Diffie-Hellman Problem, which demonstrated that it's hard to get $P_{inv}$ from $P$.

Does anyone know of a paper that uses $P_{inv}$ or uses published public "inversions"? of keys in this way?


texts: Is a tweakable block cipher still considered deterministic in nature?

texts:
"a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called blocks, with an unvarying transformation that is specified by a symmetric key. - Wikipedia "

But with a native tweak support inside a block cipher, one can achieve "varying" transformation with same symmetric key but different tweak. i.e probabilistic encryption without changing the key or using the block cipher in some mode .

Now is a block cipher with native tweak support still considered a deterministic encryption ? The only determinism being the length of the output (that is same as length of the input).


texts:
Show The function $mult(a,b)$ is weak one way if the Integer Factorization Assumption is true.

I am read the proof of this enunciated but I want know if I understand this in my way. The proof use the lemma:

  For $k$ big, the probability for one number with $k$ bits, choosen in random form, is prime is greater than $1/k$.

If I choose two numbers the probability that they are prime is $1/k^2$. Using this fact, I will be able to say given the fact that for the probability $ 1 / k ^ 2 $ a mult function is difficult to invert, then to $1/k^2$ cases the mult function will fail, then as $1 / k ^ 2$ is not negligence. The proof is completed.


texts: Secure MAC implies that probability of same tags on different messages is negligible

texts:
So let any secure MAC (message authentication code) be given.

Intuitively, I think it is clear that the probability of getting the same tag on two different messages is very small, i.e. negligible. I want to prove this statement mathematically.

How can we

formulate this in an exact manner (because, negligible in what? I guess negligible in $|k|$, where $k$ is the chosen key - I am not sure about this)
(once we have a precise formulation) prove this statement?

Supposing that this probability is not negligible, we'll have to construct a PPT adversary $\mathcal A$ that, somehow, is able to "beat" the system (which would be in contradiction with the fact that the MAC is secure).


texts: Short and to the point. I'm assuming that it is not a kind of hash function that can be used universally. After having read about universal hash functions used with the one-time pad to form an authentication scheme, these things have bugged me out.


texts: Is error propagation desired in modes of operation

texts: I'm taking a very simple class on cryptography. The class is not mathematical is just the very basics. We learned about modes of operations recently (such as CBC and CTR), one of the things I learned was about error propagation. I just don't quiet understand if this is a desired effect or not. Sorry for such a simple question, but unfortunately my class doesn't have textbooks, it's just slides, and when I have questions is difficult to look for answers. Thank you.


texts: Can an attacker recover the key if a Poly1305 collision is known?

texts:
Suppose that messages $m_1$ and $m_2 \neq m_1$, both known to the attacker, are both MAC'd through Poly1305 with the same key.  By chance, these two messages hash to the same value.  The attacker knows that $\operatorname{Poly1305}(m_1) = \operatorname{Poly1305}(m_2)$ but not the values of the auth tags (e.g. if they were passed through Blake2 with a secret key).

What attacks can the attacker mount? Can the attacker recover the secret key?

What if Poly1305 is replaced by GHASH or VHASH?


texts: Why are the right halves kept unchanged in Feistel networks?

texts:
As I'm going through the Feistel network in the DES algorithm.

While encryption uses a Feistel Network, the input block is divided into two halves left ($L$) and right half ($R$). In each round, the right half $R$ goes through unchanged. But the left part $L$ goes through an operation $F$.

I didn't understand why right halves is kept unchanged in a Feistel Network. Can anyone explain?


texts: Discrete logarithm problem particularly hard for Schnorr groups?

texts:
The Wikipedia article on Discrete Logarithm just states without source:

  In some cases (e.g. large prime order subgroups of groups ($\mathbb{Z}_p)^×$) there is not only no efficient algorithm known for the worst case, but the average-case complexity can be shown to be about as hard as the worst case using random self-reducibility.

To my understanding "large prime order subgroups of groups ($\mathbb{Z}_p)^×$" are also known as Schnorr groups. But apparently not everybody calls them that (?).

So where would I find a (citable) proof that the discrete logarithm problem is (assumed to be) hard for elements of a Schnorr group?

This is probably related to Why does Schnorr's Digital Signature scheme necessitate two prime numbers?, which would be my next question. The answer given there may be correct but also without a citable source...


texts: Is it possible to determine public key if you know private key?

texts:
Is it possible to determine public key if we know private key?

Employees has RFID card and RFID is a private key for employee.

I want to encrypt some user's (employee's) data with employee's public key, but I don't want to anybody read encrypted data without employee's RFID card.

My idea is that If we can use some function which will create public key based on RFID as a private key, than we can store that public key in rest of data of employee so encrypted data can be read only if we have RFID private key.

Is this possible and which function are you suggest?


texts: Decomposing a vector of random bits into constituent XORed vectores

texts:
Suppose I have N potential predefined, publicly known (pseudo?) random bit vectors:

sequence 1: 1001000101010111001...
sequence 2: 0100101011101010100...
...
sequence n: 0101101010111010001...

Suppose you randomly choose a few (call it m) sequences and XOR them bitwise into a final vector. If one wanted to find out which vectors made up the final vector, the only solution that comes to my mind is to enumerate the n-choose-m combinations and start ruling out sets of m.

Is there a way to be smarter about this?  Is there a way to start ruling out individual vectors instead of just the combinations of m?

Also, does the practice of XORing many pseudorandom vectors have a name?


texts: Finding the probability of a message encrypting to a given ciphertext

texts:
I have been watching a crypto course and when they wanted to prove that the OTP is a secure cipher they refer to the probability and what I can't get so far is the understanding of this notation ?

$$P(E_k(m)=c)$$

The probability of a message encrypted to a cipher? How is that?

The general formula is:

$$P(m=m∗|E_k(m)=c)=P(m=m∗)$$

where

$m$ is the message to be encrypted
$m∗$ is the message that the attacker guesses
$c$ is the cipher text
$E_k$ is the encryption function


texts: Intuition Behind Commitment-Challenge-Response a.k.a. Sigma Protocols

texts:
In How To Prove Yourself: Practical Solutions to Identification and Signature Problems, Fiat and Shamir introduce a zero-knowledge identification scheme where

The prover sends a commitment to the verifier
The verifier sends a challenge to the prover (in shape of random coin tosses)
The prover sends a response to the verifier
The verifier checks if the response is correct

This is zero-knowledge and a Sigma protocol as described by Cramer in his PhD thesis.
My only experience with commitments is in fairly flipping a coin over telephone, in which case a commitment seems perfectly reasonable.
But what is the basic intuition behind the commitment in the Fiat-Shamir case? Challenge and response are obviously part of the protocol, but why is the commitment needed? As far as I can tell, the commitment is not even revealed to the verifier in the Fiat-Shamir identification scheme!


texts: What is an "anonymous admissible timestamp"?

texts:
Can anybody explain the term "anonymous admissible timestamp" to me? Could you show a case where it is useful to apply it?

I came across this term in the comments of a question on the StackExchange Computer Science site.


texts: Encoding an element in $r=r'||h(r')$ way

texts:
We consider a finite field $\mathbb{F}_p$, where $p$ is a large prime e.g. 256-bit.

We have $b$ a fixed element of the field. We encode it as $b'=b||h(b)$, where $h(.)$ is a cryptographic hash function. Assume the output of $h(.)$ is of size 160-bit.
We encode that way to distinguish the element $b'$ from a random element $r$ of the field.

So to check if the element has the above structure we do:

(1) Parse the value: $r=r'||r''$, where size of $r''$ is 160-bit.

(2) check: $h(r')\stackrel{?}=r''$

Question1: How can we show/prove that the random element only with a negligible probability can have such structure?

Question2: Can we reduce the $h(.)$ output size to 80-bit (which is not the standard hash function output size) and set $p$ as smaller prime number (e.g. 128-bit )and prove a random value can have the above structure with only negligible probability?

Citing a paper that use/prove such statement would suffice.


texts: Fast reduction in $GF(2^{128})$ using x86 `PCLMULQDQ`

texts:
Modern x86 CPUs support the PCLMULQDQ instruction, which does an XOR-multiply of two 64-bit numbers instead of an add-multiply (i.e. typical arithmetic multiplication).  This makes XOR-multiplication for $GF(2^{128})$ significantly faster.

However, it's only one half of multiplication in $GF(2^{128})$: after the XOR-multiply, you get a 256-bit result, which then needs to be reduced by the modulus (0x100000000000000000000000000000087 for Galois/Counter Mode).

How does one do XOR-division when the CPU's hardware acceleration is only for XOR-multiplication?  I thought of using the CRC32 instruction for doing the XOR-division step, but sadly, CRC32 hardwires the modulus as 0x11EDC6F41.


texts: Can an encrypted message be derived from only keys?

texts: I recently started teaching myself cryptography, and had an idea while reading up about basic ciphers. Instead of passing ciphertext between Person A and Person B, which can be broken if intercepted by Person C, what if they passed keys between them for a ciphertext they both possessed with multiple messages encrypted in it? If Person C intercepted multiple keys, could they derive the ciphertext from them?


texts: Can I use a fixed IV with AES-GCM if I only encrypt unique plaintext values?

texts: My use case guarantees that all plaintext values are unique. In this case, is it safe to use a fixed IV with AES-GCM to carry our encryption/decryption?


texts: Calculating differentially private average of a dataset

texts:
I was looking into Google's DP library and its implementation of bounded DP-average. The library implemented DP-average following the algorithm presented in Li et al.[1].
Algorithm 2.3, calculates the DP-average from DP-Sum and True-Count. My question is if it is possible to improve it by adding noise to the true mean?
For instance, Let's assume there are N sets and each set can have 0 to 100 elements in it. Then the sensitivity of the DP-average should be (100/N). On the other hand, the sensitivity of sum-mechanism is 100. Instead of using the sum-mechanism, we can add Laplace noise with true average as follows.
DP-average = True average + laplace (100/N*epsilon)
Isn't this going to add less noise to the DP-average compared to Algorithm 2.3? This will further allow for smaller epsilon.
[1] Li, Ninghui, Min Lyu, Dong Su, and Weining Yang. "Differential privacy: From theory to practice." Synthesis Lectures on Information Security, Privacy, & Trust 8, no. 4 (2016): 1-138.


texts: Research topics related to cryptography and Hamiltonian cycles

texts:
I am very interested in pursuing a research where I can show an application of Hamiltonian cycles in Cayley graphs of some group such as reflection groups to the field of cryptography.

But currently I can't figure out where the existence of such a cycle will become important in cryptography and how to develop any useful finding as research output.

Can anyone suggest me an idea to start? An approach?

Thanks a lot in advance.


texts: What does this notation means $\mathbb{F}_{2^{-}}$?

texts:
I have seen various papers to use this notation $\mathbb{F}_{2^{-}}$ to describe the diffusion layer. As for example the permutation in AES (MixColumns).
So, we have a field with order of 2, what does the minus sign means?

I have tried to search for the term in finite fields lectures and papers but none explained what it actually means.

Here are couple of references: (and generally i have seen it used when they discuss about the diffusion layer)

On sbox affine equivalent page2

Progress in Cryptology

The new codebreakers


texts: Possibility of applying a homomorphic MAC on vectors

texts:
The basic idea of homomorphic MACs is that a user can use a secret key to generate a set of tags $σ_1 \dots σ_n$ authenticating values $D_1 \dots D_n$ respectively. so, anyone can homomorphically execute a program $P$ over $(σ_1 \dots σ_n)$ to generate a short tag σ that authenticates $m$ as the output of $P(m_1 \dots m_n)$.
The authentication tag of a message $m \in Z^p$  is a degree-1 polynomial $y(z)$.

Could this tag be generated for message expressed as vector of $n$ scalars?


texts: Can error correction and detection be done without adding extra bits?

texts:
I have gone through error detection and correction techniques like Hamming codes, and BCH codes require extra parity bits for detection and correction. While sending data, we always seem to introduce error correction by adding parity and use parity while checking for errors.

Can error detection and correction be done without adding any extra bits?


texts: Comparing two encrypted numbers using El Gamal without using decryption

texts:
I'm trying to create a protocol for comparing two El Gamal encrypted numbers (both numbers are encrypted with the same public key). However I'm having trouble with figuring out how to do this without using decryption at all.

My current approach for comparing $\mathcal{E}_{pk}(a)$ and $\mathcal{E}_{pk}(b)$ is to encrypt a random value: $\mathcal{E}_{pk}(r)$ and then calculating: $\mathcal{E}_{pk}(ar)$ and $\mathcal{E}_{pk}(br)$. By then decrypting both products and evaluating $\mathrm{max}(ar, br)$ it becomes possible to know which value is largest, without learning anything about $a$ or $b$ (with some caveats of course). However this does involve decrypting two values, which of course requires a private key. As such this approach is not ideal.

Is it possible to do this without having to use decryption?

Edit: As per request, I'll expand a little bit on what it is I'm trying to do.

I have an encrypted database on a server. The database is really nothing more than an encrypted key/value store. In this database multiple users have stored multiple records each encrypted with their own public key.

I now want to add the functionality that a user can search their own records. My idea was that the user sends their encrypted query (for example: "All my records with a value greater than $a$", where $a$ is some encrypted value) to the server.

The server then retrieves all the records belonging to the user performing the query and for each record performs a homomorphic comparison $\mathrm{compare}(\mathcal{E}_{Pk}(a),\ \mathcal{E}_{Pk}(v_i))$ (where: $v_i$ is the value of record $i$) to find all the records which have a value greater than $a$.

Lastly the server sends all the encrypted records back to the user whom will then be able to decrypt and view them.


texts: Staying PCI compliant while upgrading encryption

texts:
I am trying to migrate my encryption methods, currently I use RSA 1024 key size and hashing with SHA-1.

This configuration is going to be deprecated soon, but 2048 key size will have my system so slow and heavy transactions. Therefore, I am thinking about keeping RSA 1024 but hashing with SHA-256 (more secure and recomended by PCI).

Does anyone know if this configuration is PCI compilant? Would I have trouble getting certificates with it?


texts: Key-Bijective Secure Symmetric Encryption Methods

texts:
In AES, an N-bit message is mapped 1-to-1 message-to-output (for a fixed key).
If we use a key with N bits, however, the key is not mapped 1-to-1 key-to-output
(for a fixed message).

So, is there any secure symmetric encryption method with a 1-to-1 key-to-output
mapping?

In the end, I'm just looking for a hash function h(m,k) with no collisions
over m (for a fixed k) and no collisions over k (for a fixed m), but it seems
easiest to leverage encryption methods research.


texts: I was wondering how you would calculate the S-box in AES. I found that you have to calculate the inverse of the polynomials in $GF(2^8)$. I found out that to calculate the inverse, you have to use the Extended Euclidean Algorithm. What I can't figure out is how do you apply this to a polynomial?


texts: Encoding numbers that can be decoded mentally?

texts:
I have a lot of objects, all of which need a particular number tagged on them so I can quickly tell the customer accordingly. But the problem is that the customer should not know what these numbers say (I write how much I buy the object for).

Is there any way I can encode them so that i can quickly decode and understand what the words mean?


texts: I am trying implement the McEliece crytosystem in SAGE. My question is How I will be able to choose the appropriate matrix $S$ and $P$?. I ask this because when I trying obtain the vector $\hat{m}=mS$ in $\hat{G}\hat{m} = Decoding(c)$ I get:  matrix equation has no solutions, even after verify that $G$ is full rank.


texts:
We are doing optimal Ate pairings using a Barreto-Naehrig curve, and I am trying to make sure that an observation I made generalizes.

We define $E$ as $y^2 = x^3 + 3$ and use the tower of extensions
\begin{equation}\begin{split}
        \mathbb{F}_{p^2} &= \mathbb{F}_p[u] / (u^2 + 1) \\
        \mathbb{F}_{p^6} &= \mathbb{F}_{p^2}[v] / (v^3 - (u+3)) \\
        \mathbb{F}_{p^{12}} &= \mathbb{F}_{p^6}[w] / (w^2 - v)
\end{split}\end{equation}

and define the twisted curve $E'$ as $y^2 = x^3 + 3/(u+3)$.

Playing around in Sage, tweaking the BN parameters and playing with curves with different prime $p$ and order $r$, I found that the order of $E'$ was $r * (2p - r)$. But I haven't been able to find any confirmation that this is always true. Does anyone know if this is true in general, or if I just found a coincidence with my (very small) sample of curves?


texts: Estimate password cracking time given Shannon Entropy

texts:
Is there some algorithm that, given the Shannon entropy of a string, compute an estimation of the time that an average home computer will take to crack the password?
Thank you.


texts: Why is 0x10001 used as an RSA exponent so often?

texts: Are there any other commonly used exponents? Why are they selected?


texts: In Pedersen Key Distribution, can the public key be persistent?

texts:
I am implementing a key distribution protocol described by Torben Pedersen in A Threshold Cryptosystem without a Trusted Party (EUROCRYPT'91). In the protocol, the $n$ parties distribute a public key for the ElGamal cryptosystem, where each party ends up with "part of" the private key and can work together to decrypt a message.

In the paper, Pedersen states that the parties all agree on the two primes $p$ and $q$, and the generator $g$ of $\mathbb{G}_{q}$. $h$ is then computed based on the individiual's choice of the private key $x_{i}$ (so that $h_{i} = g^{x_{i}}$ and $h = \prod_{i}^{n} h_{i}$).

If $p$ is sufficiently large, can the public parameters $p$, $q$, and $g$ be reused? It seems to me that if in each round of encryption, each party selects a new $x_{i}$, thus resulting in a new $h$, that the values of $p$, $q$, and $g$ can be persistent.

I ask this because finding a random safe prime of 1024 bits can be slow, and finding a generator of $\mathbb{G}_{q}$ can take a very long time. If these could be agreed upon well in advance and then reused, it makes the protocol more practical.

If $(p, q, g)$ can be reused, is this true for ElGamal in general?


texts: Is it possible for a simulator to always abort?

texts:
In this paper of J. Baron, et al. (PDF), simulator always aborts the ideal functionality before client outputs its pattern-matching result obtained from the ideal functionality. (See bottom of page 30, and top of page 33)

My questions are:

Why should simulator always abort?
While simulator always abort, is it possible for adversary to distinguish between ideal and real worlds? Since, in ideal world simulator always abort and client will never output anything.


texts:
Shuffle proofs enable a prover to show that a vector of commitments or encryptions $(c_1, \dots, c_n)$ is permuted into a vector of commitments $(c'_1, \dots, c'_n)$ without revealing the permutation itself. There are plenty of papers dealing with this topic.
I am aware of the two commonly named applications:

Voting, where a semi-trusted server opens a permuted list of the votes to hide who voted for who.
Mix-Nets, where servers in the network shuffle incoming messages to hide the relationship between sender and receiver

Soft Question:
Beyond those two applications, where are shuffle proofs used/needed?
In particular, I'm also interested in applications (including blockchain related applications) that currently may not use shuffle proofs, but would benefit from them if really efficient proofs would exist.


texts:
I am doing a password manager in Java. But now I am VERY confused because of the encryption. There will be the program login, where the user types its password, and it compares to a SHA512 hash. If it matches, the user logs in, if it doesn’t, then the user doesn’t login. I think there is no problem at this point.
And then, I am using AES to encrypt the user saved passwords. The user logs in, and then clicks on an "decrypt" button to decrypt his saved passwords.
My problem is, how am i going to do this? Because I thought for a bit, and... the decryption key must be saved somewhere. But it cant be in plain text... PLUS it needs to be exactly 16 chars long.
I created a thread on Reddit - http://www.reddit.com/r/java/comments/2awvjt/storing_encryption_key/
They give me several options, but none seems to be what I want. Why? Let's see 3 options a user gave me:

Store the encryption key. Not secure in the least

User has a password that is used to encrypt the encryption key - Pretty secure and usable

User has a private encryption key that you don't store. Very secure, very usable.

Well these are my opinions:

Obviously I’m not going to use that one, since the key will be stored in plaintext.

Well, I can hash the encryption key! But the hash must be stored somewhere! And its the hashed encryption key that’s going to be used to decrypt the user passwords... so I can use 16 chars of it. It is not user friendly if the user needs to set and remember a 16 char password! So i guess this is NOT secure

If I don’t store it, how am I going to decrypt it?

So, what can you suggest me?


texts:
Whenever a ciphertext is decrypted using a block-cypher, we need to remove the padding. There are different ways to add padding, but they usually set the last byte of the last block to the number of padding bytes that were added and need to removed (e.g. we added 5 bytes, so we set the last byte to 0x05).

My question is: why do we need to verify padding? Why not read the last byte, remove that many bytes from the message, and be done with it?

Emitting a padding error sometimes catch integrity problems, but opens one to attacks like Padding Oracle, which is able to retrieve the entire plaintext in certain situations. It seems to me this is a terrible trade-off. What's the reasoning behind padding verification?


texts: Does the use of English words weaken diceware passphrases

texts:
A Diceware passphrase is constructed from a set of words chosen from a 7776-word database, using five dice throws to choose each word. The argument is that each word in the phrase adds about 12.92 bits of entropy since $\log_2(7776)≈12.92$. As Arnold Reinhold, the creator of Diceware, explains, the entropy comes from the size of the database, not from the way in which the elements are represented. So, in principle, it does not matter whether a 7-word passphrase is formed as 7 English words from a Diceware database, the original 7 five-dice throws (in effect 7 five-digit base six numbers with each digit increased by 1), or seven Chinese characters chosen from a database of 7776 Chinese characters. Each would have an entropy of about 90 bits.

Is it not the case, however, that using English words in place of the underlying dice-throw numbers reduces the entropy of the passphrase. The words in the standard Diceware database have an average length of 4.2 characters. This means that the average length of a 7-word passphrase would be about 30 characters. It is said that letters in English text have an entropy of about 1.3 bits each due to the redundancy of the language. This would imply that, analyzed as English text, the passphrase would only have an entropy of 38 bits. Arguably a Diceware passphrase is not typical English text, but presumably one could do a similar analysis to determine the redundancy of text drawn from the Diceware database, but, if my argument is correct, each letter in the passphrase would have to have at least 3 bits of entropy in order not to downgrade the entropy of the underlying Diceware elements.

Reinhold himself glosses over this. He says:

  But, you might ask, Diceware is made up mostly of English words. Doesn't that redundancy affect it at all? Well, it does. The seven word Diceware passphrase we talked about above would average about 30 letters in length (36 if you count the spaces between the words). If those letters were selected randomly, you would get 4.7 bits of strength per letter. That would work out to a lot more than the 90 bits Diceware claims for a seven word passphrase. The difference is the redundancy of English at work. However English redundancy does not affect the calculation that each Diceware word has 12.9 bits of randomness, which is based entirely how many different words there are in the Diceware list. You can rely on that number.

The redundancy of English does not affect the entropy of the Diceware passphrase, so long as you can rely on each letter having 4.7 bits of entropy, or indeed at least 3 bits. But I don't see what guarantee there is that this is the case.

Note that this question is not answered by Can an attacker exploit the nonuniform distribution of letters in a diceware password to improve a brute force search? since this question raises a different argument not considered in that question. The underlying issue is similar, but the question asked about it is different.


texts: Encrypting many small messages (log-lines)

texts:
What would be the best way of encrypting small mesasages to be stored in encrypted form? (This sounds like somthing a textbook would cover, but I haven't found any references).

Let's say I have many systems producing messages (log-lines) which I would like to transfer and store centrally in a secure manner. Using off-the-shelf products I could secure the transfer and storing of these messages independently, but I would like to investigate another approach: encrypting each message at the sendig system with the public key of the reciever, so that the messages can be stored as-is, and thus provide end-to-end encryption from the sender down to the storage medium.

First some definitions:

RSA(PublicKey, Message) means: RSA-encrypt Message with the given Key
AES(Key, IV, Message) means: AES-encrypt Message in CBC-mode with the given Key and IV
Message = gzip(plaintext)

I have come up with the following options:

I can encrypt each message with RSA:

Ciphertext = RSA(PublicKey, Message)

However, this would fail of the message is too long.

Or I could create a random AES-key for each message (and also use this as IV):

Key = Random()
EncryptedSessionKey = RSA(PublicKey, Key)
Ciphertext =EncryptedSessionKey, AES(Key, EncryptedSessionKey, Message)

However, RSA-computation is heavy and I probably cannot afford to do this for every message.  Thus, I can re-use the key for, say, 100 messages and do:

Key = Random() (re-key every 100 messages)
EncryptedSessionKey = RSA(PublicKey, Key)
IV = Random() (new IV for each message)
Ciphertext = EncryptedSessionKey, AES(Key, IV, Message)

The last one seems to be both secure and efficient. However, I really don't want to invent a system like this myself. Is there any best practices, research or textbook-examples I should look into?


texts: On Linux, seeding /dev/urandom does not unblock /dev/random, causing libsodium to hang?

texts:
Edit for clarity: Does the "standard" test for initialization of the Linux non-blocking entropy pool, by attempting to read 1 byte from /dev/random, ignore seeding of /dev/urandom from file at boot, resulting in unnecessary hanging of any code that employs the "standard" test?

This article describes the Linux kernel as implementing three entropy pools; an input pool which feeds the CSPRNG and two output pools that are fed by the CSPRNG. One output pool is a blocking pool accessed by /dev/random and the other is a non-blocking pool accessed by /dev/urandom.

This answer describes how the kernel prioritises the seeding of the non-blocking pool at boot time:

  the first 128 bits of entropy which the system collects get mixed
  directly into the nonblocking pool, bypassing the input pool
  [...]
  And per
  http://lxr.free-electrons.com/source/drivers/char/random.c?v=4.5#L677,
  nonblocking_pool.initialized is set when its entropy_total exceeds 128
  bits. So by the time anything is available from /dev/random,
  /dev/urandom has been seeded.

Virtual machines without access to entropy from the host kernel, headless devices, and low end hardware, may not provide sufficient entropy at boot to seed the non-blocking pool, leaving services which access /dev/urandom such as SSH and OpenSSL vulnerable. 'Mining Your Ps and Qs' suggest this "boot-time entropy hole" may be the cause of duplicate SSH and TLS keys.

To check that the non-blocking pool is seeded, a method is proposed in the question, answered categorically 'yes' in the answer above:

  if I succeed at reading a single byte from /dev/random, does this
  imply that /dev/urandom is seeded?

Elsewhere, this method is claimed to be the norm:

  the standard way to wait until the system entropy pool is seeded is to
  read a single byte from /dev/random

It seems that this is the approach adopted by libsodium according to this github comment and the source code, causing PHP to hang on initialization for 3-5 minutes after boot on the type of systems described above. My own experiments replicate the 3-5 minute hanging on a VPS with low-end hardware, unless additional entropy is provided by rng-tools or PHP is compiled without libsodium.

All modern Linux systems save a random seed, usually 512 bytes, at shutdown and seed the non-blocking pool with this file early in the boot process. The standard method is described in the man page for random as well as the kernel source code for random.c, and implemented in the VPS I used.

The fact that libsodium causes PHP to hang despite the non-blocking pool being seeded during boot leads to the following questions:

Is it the case that seeding the non-blocking pool as above, essentially cat /etc/random-seed > /dev/urandom, does not unblock the blocking pool?
If so, is there no better approach for libsodium to test for seeding of the non-blocking pool? (auxiliary: what method does getrandom() use to test that "the urandom source has been initialized"?)
Which pool is seeded by the above approach? My guess would be that the seed is going straight into the non-blocking pool, bypassing the input pool. The random man page and source code for random.c refer to "the entropy pool", but this is imprecise.
If the blocking pool is unblocked by the above approach, then why is libsodium hanging? The libsodium usage manual suggests an entropy count less than 160 could cause initialization to hang, but I don't see where in the source code this would be the case.


texts: MICKEY 2.0: Mutual irregular clocking, register states

texts:
I'm trying to understand how MICKEY 2.0 works in detail.

In [1], page 6, it says:

  ... the state of the generator does not repeat within the generation of a single keystream sequence ...

What consequences does this have? As the internal state generates the output, I think that two identical inputs within the same keystream sequence therefore have different outputs. Or are there any other reasons for this?

Further, on page 6 it says:

  The influence of R on the clocking of S also prevents S from
  becoming stuck in a short cycle

As I read, a short cycle in this context is a sequence of continuously recurring states. Because the state of S depends on the output of R (whose states do not repeat), also the state of S does not repeat within the generation of a single keystream sequence. Is that right?

What exactly is meant by the mutual irregular clocking? I think that this refers to the dependence between register R and register S (see Fig. 3, page 6). The output of each of them depends on the state of the other one. As they are not clocking in regular time intervals, the term irregular clocking is used.

[1] http://www.ecrypt.eu.org/stream/p3ciphers/mickey/mickey_p3.pdf


texts:
I read from PGP spec RFC 1991, section 6.1 (August 1996):

The exclusion of the other fields ensures that detached signatures are exactly the same as attached signatures prefixed to the message. Detached signatures are calculated on a separate file that has none of the literal data packet header fields.

Can anyone explain this a little bit?
Suppose I got an email message, PGP would convert the msg as "literal data packet", and then sign on it. The signature could be stored in other place (i.e. detached). but the signature will be same as storing the signature with the msg, i.e. "attached signatures prefixed to the message".
Do I get it right?


texts:
For handling variable-length input and having the calculation of the MAC remain online, encrypting the output of CBC-MAC with a second key is recommended. I have not seen it said that a different key is required, but that that appears to be the implication. I don't see why a different key is necessary for encrypting the last block. Double encryption with the block cipher $E(K, X): \{0, 1\}^{\ell_{K}} \times \{0, 1\}^{\ell_{X}}$ could be rewritten as $F_{1}(K, X) = E(K, X)$. Then, the entire MAC procedure can be reformulated as:

$m$ is the number of message blocks to be authenticated.
$M_{i} \in \{0, 1\}^{\ell_{X}}$ is the $i$th zero-based message block to be authenticated where $0 \leq i < m$.
$t_{0} = F_{1}(K, M_{0})$.
For $0 < i < m - 1$, $t_{i} = F_{1}(K, t_{i - 1} \oplus M_{i})$.
The MAC, T, is calculated from $F_{2}(K, t_{m- 2} \oplus M_{m - 1})$.

With two calls to the block cipher, $F_{2}$ is a different function than $F_{1}$, the same way $E(K_{0}, X)$ is a different function of $X$ than $E(K_{1}, X)$.


texts: Secure multiparty sum computation corruption bound

texts: In Section 3.4 of the book Secure Multiparty Computation and Secret Sharing, it is claimed that for a secure multiparty computation problem with $n$ parties, the optimal corruption bound (concerning passive adversaries and information-theoretic security) is $n/2$, that is, at most $n/2$ passive adversaries are allowed in order to have information-theoretic security. It is claimed that this bound is optimal because there exist functions that cannot be computed securely if there are $\geq n/2$ adversaries. In particular, in the first paragraph of Section 3.4 of the book, there is one sentence: the multiplication subprotocol breaks down. The book and other papers provide analysis for Boolean functions, e.g., AND, OR and XOR functions. My question is: What is the corruption bound for secure multiparty integer sum computations? More specifically, given $n$ parties $P_1,\cdots,P_n$, each $P_i$ holds a secret integer $x_i$ (assuming that all $x_i$'s are inside a finite field $\mathbb{F}$) and they want to securely compute $S=\sum_{i=1}^nx_i$. Inside these $n$ parties, $t$ of them could be semi-honest adversaries and we are concerned with information-theoretic security. Also assuming complete communication graph. I am trying to apply the Shamir's secret sharing scheme. For this problem, is the corruption bound $t<n/2$ or $t<n$?


texts: What is the difference between a random oracle and a probabilistic algorithm?


texts: What is the starting point of Hellman's TMTO method?

texts:
I understand what is happening and how the endpoint is computed but I'm still a bit unsure of where "SP" (Staring Point) came from. Are the starting points, randomly selected keys from the key-space n?

for example...


texts: Algorithm for n-of-m keys with partial results

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

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

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

The only allowed operations are:

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

Explicitly forbidden scenarios:

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


texts: Why can't we find $d$ if we know $e$ and $n$ in RSA?

texts:
Say, we have RSA public key $(n,e)=(221,7)$,

and the encryption of the message $m=12$ is $$c=m^e \bmod n= 12^7 \bmod (221) = 194 \bmod (221)$$

Can we find the $d$ by solving the equation;

$$194^d \bmod(221)=12$$

I get that the numbers I used are way smaller than they are in real life, but this should be easier then just guessing $p$ and $q$ from $n$ right?


texts:
Quality of RNGs is an important issue.

As a very basic question I would like to understand, how "poor" entropy of a RNG can help an attacker to find out the whole secret.

In my naive view, even is a RNG (e.g. of 128 Bit) is not perfect in terms of entropy, but deviates, lets say ~0.1 % from the perfect value 128, so that it has only Entropy 127, how can an attacker find the key? Guessing the remaining 127 Bits would also be an infeasible task - ??? So what can he practically do?

I would also appreciate a good source for reading.

thanks ;-)


texts:
Assuming this setup: A prime $p$, a generator $\alpha$ in $\mathbb{Z}_p^\ast$. Alice chooses her private exponent $d$ from $[2, p-2]$ and calculates her public key $\beta$ = $\alpha^d$.

Bob then chooses his private key $i$. The resulting masking key $k_M$ used to encrypt the message is then calculated as $k_M = \beta^î$.

I wondered if the following attack is mathematically possible:

If $\beta$ turns out to be $p-1$, there will be only two possible results from the $k_M$ exponentiation being $1$ and $p-1$. This is because the element $p-1$ in a cyclic multiplicative group always has $ord(p-1) = 2$, so only those two elements can be generated by $\beta$. This in turn means that only two masking keys $k_M$ exist. The attacker can then easily try those two keys and will immediately be able to decrypt the message.

Can you confirm whether this attack will work and, if yes, if real-world ElGamal implementations are vulnerable against it?


texts: IS zk-SNARK not suitable for constructing anonymous authentication scheme?

texts:
zk-SNARK was a powerful tool for privacy-respecting e-cash. However, recent years, in the literatures about anonymous authentication scheme, such as group signatures, anonymous credential, blind signature, etc., the construction of these schemes did not use zk-SNARK as the NIZK tool, but traditional ways(Fiat-Shamir transform in ROM or CRS-based Groth-Sahai NIZK). So, my questions are:

If one use zk-SNARK as NIZK tool in an anonymous authentication scheme, will it lead to some effiency or secure problems? and why?
Can the zk-SNARK only be used in Blockchain-based privacy-preserving schemes or verifiable computation?

In other words, I wanna construct a group signatures/anonymous credential scheme by using zk-SNARK, due to its "succinct" proof. But for now I haven't found any literature about this counstruction method for group signatures/anonymous credential scheme. So the above questions are presented.


texts:
I'm looking for feedback on whether or not this is the proper way to approach password verification without transmitting the actual password. Are there any problems with this scheme.

We are working on a cloud based encrypted file system and have implemented the following steps to verify that the entered password is the same when entered a second time on a different machine. All implementations are from the Microsoft .NET Framework 4.0 (Client Profile). Also, all communication is SSL/HTTPS.

Initial activation for a file system

RNGCryptoServiceProvider is used to create two 128 bit random salts (s0, s1)
Rfc2898DeriveBytes is used with the entered password and s0 with 20,000 iterations to create the 32 byte key (k0)
s1 and k0 are appended to produce b0
SHA512Managed uses b0 to produce the hash (h0).
h0, s0 and s1 are encoded as base64 and sent to the server to be persisited.

Password verification on second client

s0 and s1 are sent to the client as base64 encoded strings
Both salts are decoded.
Rfc2898DeriveBytes is used with the entered password and s0 with 20,000 iterations to create the 32 byte key (k0)
s1 and k0 are appended to produce b0
SHA512Managed uses b0 to produce the hash (h0)
h0 is base64 encoded and sent to the server. If the hash matches the original hash now stored on the server the server responds with true, otherwise false ie: password does not match.

If all is good k0 is used to actually encrypt/decrypt the file system locally using AES-256.


texts: Can ideal functionalities share variables

texts:
I am trying to define an ideal world for a protocol that requires two functionalities to interact with each other. Lets call them $\mathcal{F}_1$ and $\mathcal{F}_2$.

Now $\mathcal{F}_1$ maintains a list of some values, say $L$. This list $L$ may be updated with every activation. Any party queries this $\mathcal{F}_1$ , the list $L$ is updated. Now $\mathcal{F}_2$ needs to use this $L$ to say verify inputs that it receives from the parties. Can $L$ simply be a shared global list, so that $\mathcal{F}_2$ can verify directly. Or do I need to do something more complicated like have $\mathcal{F}_2$ query $\mathcal{F}_1$ each time (to retrieve $L$ )a party sends an input to $\mathcal{F}_2$.

Basically, are global variables allowed in UC? What are the things I need to keep in mind, if I have shared global variables in the ideal world.


texts: Which is the smallest safe elliptic curve (bit-length)?

texts:
At https://safecurves.cr.yp.to/ some elliptic curves are listed which passed certain security tests. The smallest bit-length of a safe curve listed there is 221 bits.
At wiki page discrete logarithm records the current record is 114bits.
Is this big gap between 114 and 221 needed?
Is there an EC which passes all those tests but using much less bit?

(use case)
For use case, an EC a little better than the current record would be sufficient. To be exact an EC using a modulo less than $2^{126}$ and a close-by cycle length (-1 to 2 bit).
Use case: Given two random points at this EC. It should be hard to compute one value out of the other with a given generator (with known curve, generator, run time values).

(more details)
The current record needed 2000 CPU cores for 6 months.
A future Quantum Computer is allowed to break it. The main user group will be private persons. Any agencies or criminals have less interest in it. It's sufficient if no private person can solve it currently in less than 3 years private PC computation time or in less than a month computation time in the next 10 years. Knowing this information has not that much value, maybe 50\$, in rare cases 1000\$ or 5000\$. Computation methods that require higher costs not worth it (power supply, total usage cost).


texts: Public Key Encryption using ECDHE and AES-GCM

texts:
Using a text book example, Alice and Bob want to communicate securely using encrypted messages over an insecure channel (the Internet). Alice and Bob have decided to use ECDH (using  ephemeral keys generated per session) and start off by each generating a public/private key pair using Curve P-256 - using SHA1PRNG  for randomness. Alice sends Bob her public key and Bob generates a secret key using Alice's public key and his private key. Alice does the same using Bob's public key and her private one.

Eve who is potentially sitting in the middle isn't able to solve the discrete logarithm problem that EC requires so isn't able to compute the secret key. If Eve was actually sitting in the middle at the right time she could have sent Alice and Bob her public key instead. I'm not sure if ECDSA plays a part here, but I have assumed that Alice and Bob would verify they are talking to each other by comparing a fingerprint of their public key through another method. Alice and Bob now have the same 256 bit secret key that they can use for symmetric AES-GCM encryption.

Question 1 - AES-128 requires a 128 bit key and AES-256 recommends a stronger ECDH Curve than P-256 - this means the secret key generated by ECDH is always going to be longer than the encryption algorithm requires. I assume the recommended approach is to use a KDF function like HKDF, but what is the security implication of taking an SHA-256 hash and using it directly for AES-256 or truncating it for AES-128 (Alice and Bob are using Java which doesn't have a native implementation of HKDF and I don't think it is a good idea to try and write your own).

Using an approved method they manage to both derive the same 128 bit encryption key. Alice starts by sending a message to Bob - she generates a 96 bit random IV (she confirms she will never use the same IV with the same key again). She specifies an Authentication Tag length of 128 bits and encrypts the message (she doesn't include any additional authenticated data). She prefixes the IV to the ciphertext and sends to Bob. Bob then recovers the IV and decrypts the message - he knows the message hasn't been modified otherwise the Authentication Tag would be incorrect.

Question 2 - What advantage does ECDSA provide in this scenario or am I mixing things up? Assuming Alice and Bob have verified the public key fingerprints belong to each other, only Bob is in possession of his private key (stored in memory for the duration of the session) - Eve is unable to encrypt a message using the correct secret key because she doesn't have the required private key? For Alice to be able to decrypt the message it must have been encrypted by Bob.


texts: Encrypt array of int for individual retrieval

texts:
I have limited exposure to cryptographic terminology, so please bear with me.

My end goal is to encrypt integer IDs, before transmitting them to a web client in a list of search results, in a way that prevents enumerating IDs.

Only the transmitting authority should be able to decrypt them. The client will select a single ID from the provided encrypted list, and return it to the authority (in order to request details). This requested ID from the client should be verifiable as authentic. Also, multiple encrypted representations for each ID should be present (the decryption function should be "surjective" relative to a single ID, so that it is not possible to determine from looking at two encrypted IDs whether or not they represent the same decrypted value, thus preventing correlating multiple searches to discover valid IDs).

Here's an ugly example I've devised: Given an array of int32, prepend each with both a 16-bit constant (verified upon decryption, used as a MAC) and a 16-bit random value (discarded upon decryption, provides the surjective quality). Then perform 64-bit blocksize ECB encryption on the resulting array of int64.

My first problem with this example is that I'm not aware of any 64-bit ECB ciphers that are common enough to find in my library (.NET). My second is that I made it up - there's probably a much more direct and less naive route already supported by existing schemes/encryption libraries. My third (less important) issue is that I'm doubling the wire size of my result set (which could be reduced by, for example, requiring the surrounding IDs to be included in the request).

Note that I'd be willing to require client-application cooperation. For example transmit a separate signature, use CBC, and require both the desired ID and the previous one in the following client request. (Note a weakness here is that by varying only one of the IDs, all valid IDs are enumerated.)

Any help, even just correcting my terminology so I can try some new Google-fu, is appreciated.


texts: Are there any attacks on the key exchange when the client and the server are using the same private key?

texts: Assume the same key pair is securely installed on a server and a single client and that the private key exists nowhere else. Can someone eavesdropping on a TLS handshake between the client and server learn anything about the private key or the session key that they wouldn't be able to learn if the client and server were using separate keys?


texts: Statistical Analysis of Cryptographic Hashing Algorithms

texts:
I was wondering how can I use NIST Statistical Test Suite to check for the randomness of output generated by a cryptographic hashing algorithm, let say SHA-256?

To be specific, how will I generate input for the suite? For block ciphers, we use key avalanche, plaintext and ciphertext avalanche, etc as inputs of the suite. Is same kind of inputs are used while evaluating a cryptographic hash algorithm, as for an S-box or block cipher?


texts: Is there a standard notation for a message concatenated with its signature?

texts:
I'm wondering what's the standard (or canonical) notation for "a message along with its signature", i.e.

$$
\mathit{Message}~\Vert~\sigma_k(\mathit{Message})
\text.
$$

Here the duplicated $\mathit{Message}$ is tedious. Is there a way to put it more elegantly?


texts: Does anyone have a copy of the paper describing the HiSeC™ algorithm?

texts:
I'm trying to create a remote controller compatible with HiSec algorithm. It's so old that “National Semiconductor” (now “Texas Instruments”) discontinued NM95HS01/02 and docs are unavailable.

Does anyone have the documentation that describe the algorithm code block if the HiSeC™ –High Security Rolling Code Generator? Maybe someone used them in an old project (at least 10 years ago) and already has the docs to implement the algorithm in a microcontroller.


texts: Could one build a symmetric encryption system that is competitive with the AES by randomly applying Toffoli-like gates?

texts:
Recall that the Toffoli gate is the mapping $T(x,y,z)=(x,y,(x\wedge y)\oplus z)$. We shall say that a function $T$ is Toffoli-like if
$T(x,y,z)=(x,y,((a\oplus x)\wedge(b\oplus y))\oplus z\oplus c)$ for some $a,b,c\in\{0,1\}$.

Suppose that our key is $m$ bits and the message we want to encrypt $\mathbf{x}$ is $n$ bits. Let $C$ be a circuit on the $m+n$ bits consisting of Toffoli-like gates which are selected at random where either the target is always in the $n$ message input bits or both the control and the target are in the $m$ key bits. Then for each key $\mathbf{b}$ there is some $\mathbf{c}$ along with functions $D_{\mathbf{b}},E_{\mathbf{b}}$ (the encryption and decryption functions) such that $(\mathbf{c},E_{\mathbf{b}}(\mathbf{x}))=C(\mathbf{b},\mathbf{x})$ and $(\mathbf{b},D_{\mathbf{b}}(\mathbf{x}))=C^{-1}(\mathbf{c},\mathbf{x})$.

Is there any symmetric encryption system similar to the above cryptosystem which has been deeply studied or is already in use?

If so, then how does such a cryptosystem compare against the AES or another symmetric cryptosystem?

If there is no such cryptosystem available, then what weaknesses do such cryptosystems have and why are they not in use?

Will such a randomly generated symmetric encryption system be practical once super efficient reversible computers or partially reversible computers hit the market?

In this paper, it takes 109664 reversible gates to implement the 128 bit key AES. By comparison 100,000 Toffoli gates seems to be more than sufficient when one randomly applies Toffoli and Fredkin gate, so I am wondering why this randomly generated symmetric cryptosystem is not in use.


texts: Is the 1st Encrypted Block Less Secure Than Subsequent Ones?

texts: It's my understanding that Electronic Code Book (ECB) produces similar cypher text for similar plaintext inputs which is not a good thing.  To get around that, Cypher Block Chaining (CBC) can be used to increase diffusion within the encrypted message.  For example an algorithm could take the previous block's cypher text and XOR that with next block's plaintext.  My question is, doesn't that make the beginning of a message easier to decrypt?  In my mind it seems like the 1st block of an encrypted message has a closer relationship to the original message (less mathematical permutations involved) than subsequently encrypted blocks?


texts: Question about the definition of a perfect cipher

texts:
I need to prove that the following encryption scheme is a perfect cipher:

Let $p$ be a prime. The secret key is a pair $(a,b)$ sampled uniformly at random from $\mathbb{Z}_p^* \times \mathbb{Z}_p$. An encryption of a message $M \in \mathbb{Z}_p$ is defined as:

$E_{a,b}(M) = aM + b \mod p$

The problem is that I don't understand what do I need show formally. What I could find regarding the definition of a perfect cipher is that knowing the ciphertext gives absolutely no information towards knowing the plaintext, or in a probabilistic language:

$\mathbb P(plaintext = P|C) = \mathbb P(plaintext = P)$, where $C$ is ciphertext.

Needless to say that it doesn't help me at all...


texts:
What I want to do is deterministically derive a secure key from an RSA private key, such that the RSA private key cannot be derived from the secure key.

The first approach that came to mind was simply using the private key (or some fixed part of it) as the seed for a PRNG.

Since the output of AES is random, another idea is to use AES to generate the secure key, using the first 256 bits of the RSA private key as the AES key, and encrypting some known data.

Can anyone verify either approach, or otherwise suggest an alternative way to do this?

EDIT
I left out the details of why I wanted to do this, to keep it focussed, but I guess it may be useful to know more:

I have an installer for a piece of server software that will run as part of a cluster. During installation, the installer will have access to a 'deployment' certificate - an X509 certificate that is used to sign certificates for each instance of the server (so, a CA certificate). Each server will also need to have access to a shared secret, which will be used to encrypt certain data that is shared between the servers (using AES). My thinking is that securely deriving  this shared secret from the deployment certificate private key during installation is a low friction way to do it.


texts: Why is writing your own encryption discouraged?

texts:
Say I want to write an encryption algorithm to communicate between me and my friend for this private use. How is that bad?

E.g. I can take the word Hello and encrypt it with a simple algorithm – for example –  take each letter and multiply its value by 2 and add 13 so that it becomes completely unreadable.

Is writing a private encryption that stays between two people discouraged or not? What's wrong with it?


texts:
So basically my problem is the odd result i get when measuring the time it takes to generate a ECDH key in java vs. the time it takes to generate a DH key.

I compare the time it takes to generate:

192bit ECDH-key to a 512bit DH-key
224bit ECDH-key to a 1024 DH-key

Now I expected the ECDH key pair generation to beat regular DH keys due to difference in key size, however that is not the case when I do it. Perhaps I'm measuring this wrong or is there another explanation.

    public void generateKeyPair() {

    try {

        keyfactory = KeyFactory.getInstance("ECDH");

        keyPairGenerator = KeyPairGenerator.getInstance("ECDH", "BC");

        //NIST EC-Curve P-224"
        org.bouncycastle.jce.spec.ECParameterSpec ecSpec = ECNamedCurveTable.getParameterSpec(EllipticCurveDiffieHellman.curveNames.get(new Integer(224)));

        keyPairGenerator.initialize(ecSpec, new SecureRandom());

    int num = 10;

        /* Warm up */
        for (int wRound = 0; wRound < 200; wRound++) {
            keyPairGenerator.generateKeyPair();
        }

        /*
         * Finding the right number of iterations such that we iterate for
         * at least 2s
         */
        for (;;) {

            long begin = System.currentTimeMillis();

            for (int i = 0; i < num; i++) {

                keypair = keyPairGenerator.generateKeyPair();
            }

            long end = System.currentTimeMillis();

            long time = end - begin;

            if (time >= 2000) {
                System.out.printf("Average keygen time: %.2f ms\n",
                        (double) time / num);
                break;
            }

            num *= 2;
        }

    } catch (Exception e) {
        e.printStackTrace();
    }
}


texts: What happens when cbc+hmac get a replay attack?

texts: If it use AES-CBC and HMAC-SHA256 for message send online, and someone try to replay attack on this message. Can the attack be successful? what will be happen when attacking?


texts:
For some reasons, I was looking into libgcrypt source code and found this.
If I understand this correctly, while asking to use /dev/random for some bytes, it actually checks first if rdrand is available (without being very explicit about it) and uses it up to 25%, which is fine I guess if it was used standalone.
Where I find it a little tricky is that it is activated by default. Also doesn't /dev/random rely on rdrand as well? Thus increasing the real % of entropy coming out of the Intel/AMD rdrand?
Isn't this a bit too much relying on rdrand closed implementation?


texts: How solving apprCVP solves NTRU key recovery problem?

texts:
I have studied the security analysis of NTRU PKC. It is known that if $(f, g)$ is the pair of private keys, which are ternary polynomials, then
$$\|(f, g)\|\approx \sqrt{4d}$$ where $f, g$ have d coefficients $-1$, $f$ has $d+1$ coefficients $0$, $g$ has $d$ coefficients  $1$ and rest are $0$.
It is known that short vectors in the NTRU lattice are (f, g) and its rotations (probably).
Further, we know that LLL algorithm solves apprCVP (approximate CVP) within a factor of $2^{n/2}$, i.e. it deduces a vector $v$ such that $$\|v\|\leq 2^{\frac{n-1}{2}}\|v\|_{\text{shortest}}$$
It is written in my notes that on solving apprCVP within a factor of $2^{\epsilon}$, where $0<\epsilon<1/2$, solves SVP.
How this holds? Please help.


texts:
I am very new to cryptography but can someone explain what exactly does 0...0 and 1...1 mean in general term. Is it that 1st and last bit can be 0,0 and `1,1 respectively and in-between bits can be anything $(0,1)$?

In case it helps… I stumbled upon this while trying to solve the following multiple choice question:

  Let F be a block cipher with n-bit block length. Consider the message authentication code for 2n-bit messages defined by Mack(m1,m2)=Fk(m1⊕m2). Which of the following gives a valid attack on this scheme?

  Obtain tag t on message m,0…0 (with m≠0…0), and then output the tag t on the message 0…0,0…0.
  Obtain tag t on message m1,m2 (with m1≠m2), and then output the tag t on the message m2,m1.
  Obtain tag t on message m,0…,0, and then output the tag t⊕(1…1) on the message m,1…1.
  Obtain tag t on message m,m, and then output the tag 0…0 on the message 0…0,m.

Please note that I do not want an answer to the multiple choice question. I merely want to know how to interpret the notation 0...0 and 1...1.


texts: Understanding how Oscar can decrypt a message in RSA

texts:
I have the following set-up:

  Bob has an RSA Cryptosystem with a large modulus $n$ for which
  the factorization cannot be found in a reasonable amount of time.
  Alice sends a message to Bob by representing each alphabetic
  character as an integer between $0$ and $25$ (that is, $A ↔ 0$, $B ↔ 1$, etc.),
  and then encrypting each residue modulo 26 as a separate plaintext
  character.

I want to figure out how Oscar can easily decrypt a message in this case. However, I don't really understand how the encryption works here.

For RSA we have

$e_k(x)=x^b\bmod{n}$

But I don't understand what $b$ would be in this case and I don't fully understand what 'then encrypting each residue modulo 26 as a separate plaintext character' implies. Would this mean that each character is encrypted as

$e_k(x)=x^b\bmod{26}$?


texts: Is prime regeneration necessary for every new session using a Diffie-Hellman key exchange?

texts:
As I understand it, bruteforcing a Diffie-Hellman generated secret key takes $P-1$ attempts to crack the shared secret, where $P$ is a very large prime used for modulus. If your $P$ is quite large, which according to the wikipedia page ought to be about 300 digits, then theoretically your encrypted data is secure.

Now, let's assume user A and user B generate a new personal secret for every session they hold. If a log of all of those sessions was stored, with a total of $N$ sessions, then in theory, given that you do not change $P$ or $G$ (where $G$ is defined as the primitive root mod $P$), the number of attempts it takes to crack any arbitrary session's generated secret should be $\frac{P-1}{N}$.

My question is, is that a giant security risk if $P$ is very large and kept static across many sessions? How often should it be updated, if ever? I am aware it increases the probability of a bruteforce attack succeeding, but is the increase something I should consider trivial?

Theoretically if someone is performing a bruteforce on this scheme, if the attack is random then am I correct in assuming that updating my prime would do me no good?


texts: Curve25519 / Ed25519 - Generate a private key from this term

texts:
I have 2 key pairs $(x_1, y_1)$, $(x_2, y_2)$.

I also have $a = $random 256-bit array and $b = $256-bit of defined values from me.

I know the values for $(x_1, y_1)$, $x_2$ and $b$. But I miss the value of $y_2$ (private key).

I have the following term:

// * = scalarmult_vartime
(a * sha512 (a + b) [0-32]) + x1 = x2

Can I solve this equation for $y_2$? $a$ is flexible, so maybe it can be derived from $b$?

Of course, I know that I can not get a private key from a public bookmark,
but in this case the publickey is the sum of the addition of a publickey
(to which I know the private key) with a value defined to me.

(This is a simplified version of ECC Curve25519: How to generate this kind of private key? / Strange key exchange mechanism)


texts: Why use HKDF for key derivation even it's not time demanding?

texts:
KDF such as scrypt is memory (cpu) demanding so that the attackers cannot quickly decrypt the key.

Why use HKDF?  What's the application of it?
If the attacker knows the input space of HKDF, and since the procedure of HKDF is public, what's the extra benefit of using it?


texts: What is the difference between a hash function and a pseudorandom function?

texts: Read the title. I've seen in RFCs that some MAC functions are called "pseudorandom functions". What are those? How are they different than hash functions? Why can't a hash function be used instead?


texts: How confident can we be that nobody will crack a 128-bit key?

texts:
In a context involving a block cipher like AES-128, excluding quantum computers, cryptanalytic breakthrough on AES and implementation attacks (poor TRNG, DPA..), and wrench, how confident can we be that by key search, "nobody will crack a 128-bit key" until 2100. Assume business as usual for humanity, use of 1 year worth of global production of electricity, 1 year worth of industrial production for the gear (used over a multi-year period).

Full disclosure: I'm trying to challenge my own half-baked opinion.

Updated: I leave it open if we allow multi-target attacks, where the same known plaintext is available enciphered under many random 128-bit keys. That makes a huge difference, but specifics of the block cipher become less important, which is good.

Note: we have a related question there; but it was considering a 256-bit key size, the methods adequate for that size need not be precise, and have not led to a definitive or even clear conclusion on 128-bit; plus answers are nearly 6 years old, and much more SHA-256 have been performed since then than I would have predicted at the time.

Note: We have another related question there at the 128-bit key level, but it restricts to currently available technology. Here, we must account for foreseeable technology more plausible than quantum computers usable for that cryptanalysis.

Note: 2100 and other limits have been set (instead of the original in the future of humanity as a species) for the sake of making a quantitative answer more falsifiable. Say, global apocalypse on that March 1 because a military subcontractor goofed on the leap year rule.


texts: Questions about the certificate authority procedures

texts:
I am beginner in cryptography and now I try to understand certificate process.

I read this answer and have some questions about the enrollment process:

  The general procedure to issue certificates in a Public Key
  Infraestructure is moreless the following.

  1) the client generates a key pair, private and public

  2) the client generates a CSR (Certificate Signing Request) including
  attributes like Common Name and the Public key. Signs it with the
  private key and sends it to the server

  3) The server builds the X509 Certificate with the CSR data, sins it
  with the CA private key and returns the X509 to client

  4) the client stores the private key and the certificate in a KeyStore

It's not clear to me when client encrypt CSR (Certificate Signing Request) by client's private key and send to CA server ---> How the Server can read this CSR?
The CA server build X.509 and sign with CA private key. If I have client B, how client B get client A public key?
I wrote the code in Android to generate RSA key pair. Next step, what should I do to get certificate from CA server?
About CA server, I find two open source: OpenCA and EJBCA. What should I choose?

I am not clear about this. Thanks in advance.


texts:
If I only need a small number of signatures (perhaps $2^{10}$) for the lifetime of my key pair, how would I calculate the consequent signature size?

Unfortunately managing state for an LMS or XMSS signature would be an issue, so that's not an option.


texts: Distinguishing between two probabilities and the uniform probability

texts:
Say I have a polynomial adversary $A$ that can distinguish with a non-negligible adventage between $x$ generated from a probability $X$ and $y$ generated from a probability $Y$.

Obviously, this implies that it is possible to either efficiently distinguish between $X$ and the uniform distribution, or between $Y$ and the uniform distribution (or both).

How can this be proven?

Can $A$ be directly used to construct another adversary that distinguishes between $X$ and uniform (or $Y$ and uniform) ?


texts: Under what conditions did a Bletchley bombe stop?

texts:
I am trying to understand the conditions necessary for one of the Bletchley Park bombes to stop. Let me give an example.

I have been experimenting with Enigma machine and bombe simulators to try to understand better how the bombe works.

Using a standard three rotor Enigma machine set up as follows:

Rotors IV-I-III,
starting with QLH
rings set to AAA
with plugs EL GK US XZ WI NV FD BY MC PQ

The following plaintext WETTERVORHERSAGE becomes the following cryptotext RRHKJKNJXEUWNFOT (see enigma simulator) .

Using this as a crib, the menu that this produces has three loops (REHTK, EHT, RETK) and a click (loop of the two letters WR), which is pretty good as a crib as this means that the bombe then returns far fewer false stops.

When I plug this crib into the following bombe simulator (where all rings are set to A) I get a collection of about twenty stops, one of which is the correct one.

So my question: what is the condition that stops a bombe that is satisfied with respect to the crib menu?

My understanding is that the back of the bombe is set up to simulate the menu and then the bombe is switched on, stopping through a short circuit when, well, when what?

I tried to use the first false stop that the bombe simulator gave me to understand: 231-YAL. So in particular, my question can be applied to this situation. What is it about this set-up that would stop the bombe with the given crib-menu?

What I did notice in this configuration is that the click is correct with respect to the letters M and T (indicating that there should be plugs WM and RT) BUT the remainder of the loops do not match.


texts: What is the best strategy to avoid getting even orders in Shor's algorithm?

texts:
I do understand Shor's algorithm wants the order of an element to be even so that it can use the factoring identity and find a non-trivial factor.  But is there a relationship between safe primes and the order of an element being even? In other words, is $N = pq$ --- where $p$, $q$ are safe primes --- the hardest integer for Shor's algorithm?

I'm not interested in order-finding.  I'm only interested in the classic-side of Shor's algorithm.  How can I slow Shor's algorithm down?


texts:
P.71 of Cryptography Engineeering states "Any weakness in CTR encryption mode immediately implies a chosen plaintext attack on the block cipher." It seems to me that "any weakness" is vague. I'm not quite getting what the author has in mind. Can someone please elaborate?

EDIT:

The purpose of the statement seems to be to highlight the relationship between the security of the block cipher and CTR mode - a break of CTR implies a break in the underlying block cipher (except information leakage and traffic analysis). I don't see how a break of CTR means the break in the block cipher is necessarily of the chosen plaintext variety.


texts: Are ring signatures possible with elliptic curves? If so how. The original paper by Rivest, Shamir, Tauman seems to require an invertible trapdoor function. But I've only seen algorithms for secret agreement (ECDH for example) with elliptic curves. That doesn't seem to be adequate to complete the ring - don't you need invertibility?


texts: Decrypting DES with decrypted and encrypted data

texts:
I got two 8-byte strings.

One which is decrypted is:

FF FF FF FF FF FF FF FF

and one which is encrypted is:

16 05 78 B0 0A C2 78 7F

Encryption mode is CipherMode.ECB

I need the key used in DES encryption.


texts: Upper bound of this derivative of counter mode?

texts:
Suppose that:

$\boldsymbol{K} \in \{0, 1\}^{\ell_{K}}$.
$\boldsymbol{IV} \in \{0, 1\}^{\ell_{IV}}$.
$\boldsymbol{I} \in \{0, 1\}^{\ell_{I}}$.
$\boldsymbol{X} \in \{0, 1\}^{\ell_{X}}$.
$E(K, X): \boldsymbol{K} \times \boldsymbol{X} \rightarrow \boldsymbol{X}$.
$D(K, X): \boldsymbol{K} \times \boldsymbol{X} \rightarrow \boldsymbol{X}$.
$E$ and $D$ are the encryption and decryption functions of a secure block cipher.
$\widetilde{E}(K, IV, X): \boldsymbol{K} \times \boldsymbol{IV} \times \boldsymbol{I} \times \boldsymbol{X} \rightarrow \boldsymbol{X}$.
$\widetilde{D}(K, IV, I, X): \boldsymbol{K} \times \boldsymbol{IV} \times \boldsymbol{I} \times \boldsymbol{X} \rightarrow \boldsymbol{X}$.
$\widetilde{E}(K, IV, I, X) = \widetilde{D}(K, IV, I, X) = E(E(E(K, IV), \lfloor I \div 2^{0.5 \times \ell_{I}} \rfloor), I) \oplus X$.
$CT_{i} = \widetilde{E}(K, IV, i, PT_{i})$.
$PT_{i} = \widetilde{E}(K, IV, i, CT_{i})$.

The birthday bound applies to counter mode, so the maximum number of blocks that can be safely encrypted using it is $2^{n}$ where $n$ is the block size in bits of the cipher that is used. The scheme above presents a modification to counter mode that uses several block cipher calls. The key used to encrypt the counter is regenerated from the upper half of the counter every time $2^{0.5 \times \ell_{I}}$ blocks have been encipher/deciphered. What is the security bound of this mode. My intuition tells me it is $2^{\ell_{X}}$. Am I correct?


texts: Security of an S-box based on modular multplicative inverse

texts:
The construction of Rijndael's S-box starts with the multiplicative inverses of each number over a finite field. It seems like this is the main source of its non-linearity. I figured that modular multiplicative inverses could be used as well. In this case, determining the value of $S(x)$ starts out with finding $y$ such that $((x + 1) \times (y + 1)) \bmod 257 - 1 = 1$.

Here is the result:

00 80 55 C0 66 2A 92 E0 C7 B3 BA 95 B1 C9 77 F0
78 63 E5 59 30 DD BD 4A 47 58 ED 64 C2 3B C6 F8
93 BC EA 31 83 72 90 2C A2 98 05 6E 27 5E AE A5
14 23 7D AC 60 76 F2 B2 F7 E1 3C 1D 3A E3 65 FC
56 49 E9 DE 94 F5 B4 18 A8 41 17 B9 F6 C8 F3 96
A4 D1 5F CC 7E 02 40 B7 19 13 D0 AF 97 D7 2D 52
34 8A 86 11 1B 3E 04 D6 A3 B0 F4 BB DF F9 2B D9
73 7B 25 70 85 9E 35 0E 10 9D 8B 71 DB 32 54 FE
01 AB CD 24 8E 74 62 EF F1 CA 61 7A 8F DA 84 8C
26 D4 06 20 44 0B 4F 5C 29 FB C1 E4 EE 79 75 CB
AD D2 28 68 50 2F EC E6 48 BF FD 81 33 A0 2E 5B
69 0C 37 09 46 E8 BE 57 E7 4B 0A 6B 21 16 B6 A9
03 9A 1C C5 E2 C3 1E 08 4D 0D 89 9F 53 82 DC EB
5A 51 A1 D8 91 FA 67 5D D3 6F 8D 7C CE 15 43 6C
07 39 C4 3D 9B 12 A7 B8 B5 42 22 CF A6 1A 9C 87
0F 88 36 4E 6A 45 4C 38 1F 6D D5 99 3F AA 7F FF

I understand that this by itself would make for a terrible S-box given its symmetry and fixed points, but perhaps some other math stacked on top of it would make it better?


texts: Is it necessary to use single hash function for signature generation and HMAC?

texts:
I am trying to figure out if we need to use single hash function across all the places in a ssh session. i.e – signature generation/verification and HMAC calculation/validation. Is it possible to use two different hash function for signature and HMAC?

I am planning to implement SHA-256 for signature generation/verification in an embedded system. But I am concerned that if I use SHA-256 for HMAC also then there will be much impact on performance considering the lesser CPU capacity of the embedded system. I am new to cryptography so I am not much aware of these things. It will be great if anyone could help.


texts: Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?

texts:
There's a classical method to efficiently test if a LFSR with $n$ bits is maximal-length (or equivalently, if the feedback polynomial is primitive), when the factorization of $2^n-1$ is available.

Do we have an efficient method working when that factorization is unavailable, e.g. because we do not want to depend on a full factorization algorithm, or on the factorizations of $2^n-1$ (for all $n<2991$, and some much higher $n$) amassed by the Cunningham Project?

For reference, the classical method goes:

Check that starting from a particular non-zero original state (e.g. the low-order bit set), and after stepping $2^n-1$ times, we get back to the original state; if not, the LFSR is not maximal-length (since it did not cycle after the maximum period $2^n-1$).
If $2^n-1$ is not prime, then for each of its prime divisors $p$

check that starting from the original state, and after stepping $(2^n-1)/p$ times, we do not get back to the original state; if we do, conclude that the LFSR is not maximal-length (since it cycled before the maximum period $2^n-1$).

Conclude that the LFSR is demonstrably maximal-length (since its period starting from the initial state is bound to be a divisor of $2^n-1$, and we checked a multiple of any divisor of $2^n-1$ other than itself in the previous step).

The algorithm is fast, because the linearity of the LFSR allows computing the state after $k$ steps in time $O(n^2\cdot\log_2k)$ and memory $O(n^2)$.


texts: What does it mean that $BW_N$ is a permutation over the squares mod N?

texts:
Let $BW_N$ be a function such that $BW_N:\mathbb{QR}_{N} \mapsto \mathbb{QR}_{N}$ and let if be defined as follow: $BW_N(x) = x^2 \pmod N$ where $N=pq$ and p and q are primes and $p=q=3 \pmod 4$. I am reading on a set of lecture notes that, "$BW_N$ is a permutation over the squares mod N". Does someone know what that means?

Does that mean its a trapdoor permutation? Or what might it mean?

I am not sure if this question would have been more appropriate on the mathematics stack exchange site, but it had to do with crypo so I though it might get a response here.


texts:
Say I have a publicly available Merkle tree, and I want to prove the existence of a leaf (containing a number, maybe) in the tree.
I could give the path along with the siblings, for a normal Merkle proof, but this reveals the leaf itself.

How can I do this in zero knowledge, i.e., proving that the leaf exists, but not revealing which leaf?


texts: Are these emerging threats against AES affecting your designs?

texts:
Recentally, an attack on AES was discovered which reduces its computationally complexity,  by a very slight amount.

The first key recovery attack on the full AES-128 with computational
complexity $2^{126.1}$.
The first key recovery attack on the full AES-192 with computational
complexity $2^{189.7}$.
The first key recovery attack on the full AES-256 with computational
complexity $2^{254.4}$.

There is also the new AES-NI instruction set, which allows attackers to make hundreds of billions of parallel guesses per day.

In light of these emerging threats, have you made changes to your designs to mitigate the impact?  If so,  what has changed?


texts:
I have a question .
How the system know the attributes of the users to be after that as a public key in ABE?


texts: Can I use an ECDH Shared Secret from the same Private / Public Key Pair?

texts:
I'd like to know if using the ECDH shared secret of a static EC Private Key with it's own corresponding static EC Public Key causes a problem / weakness.

(edit) not asking if it's ok to re-use the keys multiple times.  Static EC Keys are known to be ok in this usage case.

Background:

In this environment, several agents are producing and consuming data, and the streams are being protected with static ECDH keys.

The ECDH Shared secret is hashed before it is used as a key in the asymmetric stream cipher. The shared secret will be the same each iteration / connection.

The stream is eventually stored to disk (encrypted)

Typical usage (not considered a problem):
$$
Alice( public ) : \ Q_A = d_A G
$$
$$
Bob( private ) : \ d_B $$
$$
ECDH Secret (Alice Bob) = d_B Q_A = d_B d_A G
$$

Normal so far...

Question Case:

In some instances, the Producer and Consumer are the same agent, and this ECDH secret devolves into:

$$
ECDH Secret (Alice Alice) = d_A Q_A = d_A d_A G = (d_A)^2G
$$

Is this a problem?


texts: Possible to know who is the owner of a message encrypted with RSA public key

texts:
Given the scenario in which I want to send 10 messages either to Stalio or Olio. I encrypt these messages with their respective public keys using textbook RSA, before sending the messages to their recipients.

Can an attacker - by knowing only the public keys of Stalio and Olio and the 10 cipher texts - tell which of those messages is addressed to who?


texts: Is it possible to fool Miller-Rabin test?

texts: It is well known that it's possible to fool Fermat test with Carmichael numbers. But, is it possible to deliberately fool many-rounded Miller-Rabin test by constructing some special number without using brute forcing strategy? I know that one round of Miller-Rabin distinguish with probability 25% that number is prime, but for many rounds brute force will become infeasible.