texts: Filter party-1 strings against party-2 white/black list keeping the lists private

texts:
Suppose I have a server and a client. The client has a list of arbitrary strings and the server is supposed to filter this list using white and black lists kept on the server side. It would be nice not to share the list of the strings to the server and the white/black lists to the client. For example, a list of open applications at the client side is sensitive data, and the white/black lists are not supposed to be exposed from the server to the outer world as well. I'm wondering whether it's possible to check the client strings against the white/black lists keeping them private at all parties. The only way I can see now is:

Client: split the list of strings to a list of split-by-whitespaces strings list and hash each element.
Server: do the same for the white and black lists.
Server: compare the client and the server hashes.

This solution has a lot of downsides. Is it possible to re-implement it in other way somehow? Or, is the idea feasible at all? Thank you.


texts: Embedded device needs PRNG, has AES & EEPROM

texts:
TL;DR - the device is just a microcontroller and essentially does whole-disk encryption. At initialization time, I need a PRNG to create the key material.

I have a software AES ECB encrypt operation (among other things - I also have CTR mode, but it isn't tooled for this use, and I have AES CMAC).

Some quick googling suggests that if I had a 16 byte PRNG key, then I could simply keep a 16 byte counter value and count from 0 for each block, run that through ECB and use that as the PRNG output.

I don't mind performing a read of /dev/urandom at manufacturing time and writing that into the controller's EEPROM.

Is it really just that simple?

Is there any reasonable alternative to pre-seeding the PRNG key (I'm guessing not)?


texts: Why does EdDSA require a b-bit private key instead of b/2-bit?

texts:
By design, EdDSA requires a $b$-bit string as the secret key $k$, and when signing, it is expanded to a $2b$-bit string $H(k)$, some bit-twiddling is done, and the first half is used as the private key in the signature. [1]

The curve will have a $b$-bit security level, and solving discrete log can be done in $b \over 2$.

Why is it that EdDSA requires a $b$-bit secret key instead of only $b \over 2$-bit which seems like it would provide the same level of security as the curve itself?


texts: Brute force integer factorization - back of the envelope calculation

texts:
RSA-240, an integer with 240 decimal digits from the original RSA Factoring Challenge, has recently been factorized.

According to the researchers, the factorization took a total of 900 core-years on a 2.1 GHz Intel Xeon Gold 6130 CPU:

  RSA-240 sieving:  800 physical core-years

  RSA-240 matrix:   100 physical core-years

Just as a theoretical exercise, I'd like to understand how this computing cost ranks against the (purely theoretical) cost of brute-forcing the factorization.

By brute-forcing, I mean basically trying out every single integer n, starting with n=2, and checking if RSA-240 % n = 0, i.e. if RSA-240 can be divided by n without a remainder. This is, of course, incredibly inefficient - we know RSA-240 to be the product of two prime numbers, and most integers n aren't primes, so there's no point in testing them. I'm kinda looking for a base line here with no optimizations whatsoever.

The factorization of RSA-240 revealed

244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447

as the lower of the two prime factors, which a decimal with 120 digits, therefore a number between $10^{119}$ and $10^{120}$. Let's call that number p and the other factor q.

So the brute force approach would have had to try that many numbers n until it would arrived at p and realized that RSA-240 % p = 0. Computing q = RSA-240 / p is then, of course, trivial.

So let's say the cost of computing RSA-240 % n is c CPU cycles.

Even if c=1 (on some specialized hardware with very wide registers), on a ~2 GHz CPU, we could check 2B = 2  x  $10^9$ numbers per second. So, checking all the numbers up to p would take approximately $10^{120} / (10^9) = 10^{110}\text{ seconds} = 10^{103} \text{ years}$ (there are 31,536,000 seconds in a year, that's about $10^{7}$) - an incredibly long amount of time, and about $10^{100}$ times as long as the 900 core-years the researchers managed to achieve.

Is my math about right, or am I missing something?


texts: RSA: how does it work and how is it more secure than symmetric systems

texts:
Before starting the question, I know that RSA is naturally a key exchange cryptosystem rather than an antilogarithm fully implemented for encrypting and decrypting data since the length of the secret data relies on the key size of RSA. Now, we know that RSA is asymmetric means it has a public key and a private key.I know that one should not be able to decrypt an encrypted key using RSA by the public key while the secret is decryptable by the private key. I've also read that (may be I'm confused and mistaken) the public key is calculated based on the private key.

Now I have some questions, when using this algorithm in C# using the cryptography namespace, we have to serialize and export the private members of the key (private key) to be able to decrypt the secret. So what is the purpose of the public key, how is it public at all, and how does it introduce a higher level of security to the algorithm.

Let's say I do the same using AES, then I'm gonna have two Keys (Key, IV) which are only shorter in size. Except for the length of key, how RSA is more secure than AES then. If I don't exchange the public key, what is the purpose of it, if I do but nobody can use it to break the secret then what is the purpose of it again?


texts: Why would you want to use a digital envelope? As I understand it, a plain-text message is encrypted using a secret key and then the key is encrypted with the receiver's public key. The encrypted message and the encrypted key is sent as the digital envelope. Now, what I don't understand is why one just don't encrypt the plain-text message with the public key in the first place? The literature I have been reading states that the secret key used to encrypt the message is a one-time key, so wouldn't this render the digital envelope unnecessary? I would understand the purpose of a digital envelope if it was to encrypt the secret key for continued communication, but according to the literature, this does not seem to be the case.


texts: Question of proving the opening of Pedersen Commitment

texts:
Given an opening $(m, r)$ of a Pedersen commitment $c = g^m h^r$, where $g, h$ are the generators of a group $G$ with prime order $q$ (public), a PPT prover wants to prove to a verifier the opening of $c$ in zero-knowledge. Let us see the following procedure. Here we note that the DLP in $G$ is hard.

Prover randomly pick $s, t < q$, computes $y = g^s h^t$.
The verifier checks whether $y \in G$. If it is, the verifier sends a random challenge $e$ to the prover.
The prover sends to the verifier $z_1 = s + em \bmod q$, $z_2 = t + er \bmod q$.
The verifier accepts if $g^{z_1} h^{z_2} = y c^e$.

It seems that this argument works for our requirements. It is complete and special honest-verifier zero-knowledge.

But for the soundness, if a malicious prover provides $z_1' \ne z_1$, $z_2' \ne z_2$, such that $g^{z_1'}h^{z_2'} = yc^e$, it seems that such a prover can cheat in the procedure above. I know that a PPT prover cannot do this except for a negligible probability. But how can we formally prove this fact? Is it possible to provide a formal reduction that, if a malicious prover can cheat in this way, using this malicious prover we can provide two openings of a Pedersen commitment? If we can't, how can we show the soundness of this procedure? In a formal proof, do we need to always provide a reduction?


texts: Reduction to security of proof system for proving knowledge

texts:
I want to prove security of my system by reduction to the security of an underlying
non-interactive proof system for proving knowledge. I know a game that captures the
desired security property of my system, and I want to reduce to an adversary's
inability to produce a non-interactive proof without a witness (since possession of the witness
suffices to win the aforementioned game), which games capture suitable properties of
non-interactive proof systems?


texts: Does adding a salt to the message before HMAC processing add any security?

texts:
An HMAC function is designed to verify message integrity, i.e., that the message has not been tampered with. It is generally (always?) implemented by using a hashing function H, and calculating the hash H(key + H(key + message)), where + signifies concatentation (Source). The key is secret, and is reused for multiple HMAC calculations.

A related cryptographic technique is "salting." This is commonly used when storing passwords: each password will have a unique salt (or "nonce"), and you store the hash H(salt + key) and the salt together in the database. The salt is not encrypted, is not reused for other passwords, and is not a "secret" like the HMAC key.

My question is: does it add any security to add a random salt to the message you are validating with HMAC?

In my situation, the "message" I am validating is a six digit number. My "gut" was to use a salt (perform HMAC on salt + my six digit number) to protect against rainbow tables, but then it occurred to me that, since I'm using a 512-bit HMAC key generated by a cryptographically secure random number generator, there may be no added security. If I'm understanding it correctly, this answer (to a question about HMACing short inputs) means that there is no added security.

However, I am not completely certain. So, can someone clarify? Is there any value in adding a salt to your message prior to determining the HMAC?


texts: Does any popular symmetric cipher allow for direct re-ciphering?

texts:
Let's say I have some data ciphered using key, $K_1$, in to format $D_1$, which I want to convert into format $D_2$ that can be decrypted using $K_2$.

So I know $D_1, K_1$ and $K_2$.

I want to convert $D_1$ to $D_2$ but I want to avoid actually decrypting the data $D_1$ into its plaintext form. Is it possible to do so for any of the popular symmetric encryption algorithms such as DES, 3DES, ARCFOUR, AES, Camellia, RC2, IDEA, SEED? I am guessing it's not possible, but still thought I'd ask, since I don't know much about most of these methods.

A reason for doing something like this may be in an enterprise setting  where companies typically create their own https proxies and act as MITM. If they only want to analyze the headers of the http packet but not the body itself then they could only decrypt a portion of the data and pass on the rest of it. This way they can be minimally invasive given their security policies.


texts:
I need to use AES-128 to encrypt a plain text about 720 bits.

Is it correct to say that – in this case – the plain text will be divided in 5 blocks of 128, the result will be equal 640 bits, and the other 80 bits would be expanded to 128 bits?

The total result would be 6 cryptograms( 5 - 128 bits, 1 - 80 bits expanded to 128 bits) that will be concatenated.

In the end, what I would like to know is: what's the correct procedure to standardize the plain text to be encrypted by algorithm?


texts: Does the multiplicative property apply to modern, non-text book RSA?

texts:
I'm aware of the multiplicative property of the textbook RSA and how it can be used to get a signature from a CA without having the CA directly signing it.

My question is - can this apply to the real world in modern implementations of RSA?

More specifically - assume I have this CA that will sign every CSR (Certificate Signature Request) I give it except a specific one, a "forbidden" one.

Theoretically, I would like to have this CA sign 2 (or more) "valid" CSRs and "multiply" their signatures to generate the desired "forbidden" signature (that one CSR the CA refused to sign)

Could this work?


texts: Is there a way of sharing a key without anyone knowing what the key is initially?

texts:
I started learning about key sharing and Shamir secret sharing, I'm wondering whether you need someone who knows the key initially and then distributes it, is this step necessary or not?
In my case I have a group of people that run a permission blockchain (they are the consensus nodes) and I want all incoming transaction to be encrypted but the decryption part should be available only if a majority decides to construct the decryption key, but I don't want this decryption key to be known initially by anyone. Is it possible or not?


texts:
While preparing for a crypto exam there is a task we don't really understand:
task
Let $E_K$ be a permutation $\{0,1\}^b \rightarrow \{0,1\}^b$ defined by a blockcipher with the key $K$. Let $M = (M_1,...,M_n) \in *(\{0,1\}^b)^n$ be an nb-bit message.
We interpret the output of $E_K$ as an integer $E_K(\cdot) \in \mathbb{Z}_{2^b}$ and define the MAC as the following:

// ungerade means odd, gerade means even
we should now provide an attack which is always successful. The restriction is that we are not allowed to perform a CPA. So we search for the a pair $(M',A')$ with $A' = MAC_K(M')$
Our problem is the restriction. So we don't know whether we are allowed to change the calculation or function in any way (furthermore would such an operation make the task way too easy).


texts: I have recently read about how blockciphers and how stream ciphers work, and although I think I finally got everything right, I'm still wondering how increasing blocksize increases security.


texts: How does openssl signature verification work?

texts:
I would like to know how openssl verifies a digital signature? I know that it uses this command to verify a signature:

openssl dgst -sha256 -verify pkypem -signature signbin msgbin > result

What I want to know is, what openssl does exactly with the public key, the signature and the message before verification.

I'm also interested in the signature creation process.


texts: Final permutation table example with DES

texts:
This question has been asked by another already but I can't comment on that.

There is a question in a book:

  Find the output of initial permutation box when input given in hexadecimal as:

$\texttt{0x0002 0000 0000 0001}$

How does this input have two 1s at bits 15 and 64?

How do I look into the initial permutation table for the output:

$\texttt{0x0000 0080 0000 0002}$

Please also give any reference material.


texts: Why do block ciphers use key schedules instead of round constants? (Even-Mansour)

texts:
Let's take AES as an example. What would be wrong with just having a 256 bit key that you XOR into your input and then XOR into your output? No key expansion at all.

I believe it's even known as the Even-Mansour construction and is secure under the assumption that the permutation is sound.

So I'm confused by the purpose of key schedules, you need variability to resist slide attacks but you don't need a key schedule for that, round constants suffice.


texts: Can specific Weierstrass curves be some benefit from Montgomery/Edward form?

texts:
I have noticed that DBL/diffadd in Edward/Montgomery form almost double fast than Weierstrass form(EFD), and curve25519 is empressive high-performance.The transformation between these forms can be covered by two ModInvs at most(even two ModMults). So the scalar multiplication in specific elliptic curves like p256 or Secp256k1 could transfer to scalar_mult in Edward/Montgomery form.

Could these tranformation&AdditionChain&diffAdd be faster than the ordinary MADD&w-NAF&preCom methods?
Of course Curve25519 is designed for Montgomery form, but the wide spread Weierstrass curves also have well-designed prime number. To what extent will the curve parameters affected the performance of Montgomery/Edward scalar_mult?


texts: Message Expansion / Encryption Blowup Factor / Ciphertext Expansion of ECC

texts:
In order to complete the following table with asymptotic times and message expansions,

$\quad \quad \quad \quad \quad \quad \quad \quad \quad$ RSA $\quad$ McEliece $\quad$ ECC

Encryption Speed $\quad \quad \; \; N^2 \quad \quad N^2 \quad \quad \quad N^3$

Decryption Speed $\quad \quad \; \; N^3 \quad \quad N^2 \quad \quad \quad N^3$

Public Key Size $\quad \quad \quad \;\; N \quad \quad \; \ N^2 \quad \quad \quad N$

Private Key Size $\quad \quad \quad \;\; N \quad \quad \; \ N^2 \quad \quad \quad N$

Message Expansion $\quad \; 1-1 \quad \; 2-1 \quad \quad \quad ?$

I need to find the message expansion of ECC cryptosystem, but I don't find a clear answer anywhere.

Can someone give me and explain the missing value in the table?

Thanks in advance.


texts: I am looking for a very difficult/slow hashing function to hash secrets used to decrypt env files. Because it is used to log when the env files "keys" get recreated I don't need it to be fast, ideally close to a full second to calculate because I will be in trouble if the keys get stolen but I want to log when I changed them and log a hash of the keys so I can debug in the future.


texts: Is the ring of octonions "commonly" used in Cryptography?

texts:
I've recently read "Fully Homomorphic Encryption on Octonion Ring" by Yagisawa, which is based on octonion rings over finite fields.

Personally I've never encountered octonion rings in cryptography before. Is there any example of them being used in previous work?

Please don't mention the mentioned previous version of this scheme.


texts: Cardinality of a set of successful hash values

texts:
Im trying to comprehend a proof from the paper "Efficient Identity Based Signature Schemes Based on Pairings"(2002) by Florian Hess. At one point of the proof for Theorem 2 I don't understand how the cardinality is concluded. Summarized my problem is the following:
We have a machine C that replays a machine B at most $\frac{2}{\epsilon_B} + \frac{14n_2}{\epsilon_B}$ times where $\epsilon_B$ is the probability for machine B to suceeds on its own and where $n_2$ is the number of queries B asks. By replaying B machine C produces two valid signatures $(\mu_1,r)$ and $(\mu_2,r)$ with message hash $h_1(m,r)$ and $h_2(m,r)$ for the same m,r. The first $\frac{2}{\epsilon_B}$ are to generate the first signature and the $\frac{14n_2}{\epsilon_B}$ replays are to produce the second signature by applying the forking lemma. The forking lemma is applied in regard to a random tape $\delta \in (\mathbb{Z} / l \mathbb{Z})^\times \times (\mathbb{Z} / l \mathbb{Z})^\times $ which is used to answer the $n_2$ queries for $h(m,r)$. Every entry of $\delta$ is used as $(v,w)$ to answer the queries. The value of $m,r$ stays the same up until the point $\beta$ where the random tape forks: $\delta =(\delta_j)$ for $j<\beta$. From this the conclusion is drawn that the $h_i(m,r)$ are randomly chosen from the set of successful hash values $\delta_\beta$  which has the cardinality $\geq \frac{\epsilon_B(l-1)^2}{14n_2}$ (with $l$ being the security parameter). Why is the cardinality of this set $\geq \frac{\epsilon_B(l-1)^2}{14n_2}$?


texts:
I've looked up RC4 algorithm and it's seems easy enough but some parts of it seem random to me.
In the key schedule part take for example the following part :

j = (j + S[i] + key[i % keylen]) % 256

I can understand most of it:

the key[i % keylen] is padding in-case that the key is shorter than 256 bytes, and
the % 256 is to ensure that j will be in the range of 0-255 when performing the swap.

But why do we need the j = j + S[i]?

Is there a mathematical explanation to this or is it just to add some randomness? Also regarding to the pseudo random generator part: can someone point me to a reference which offers an explanation for the not so obvious operations?

I've looked for explanations on the internet but couldn't really find anywhere that explain those bits.


texts: Is there a string that's hash is equal to itself?

texts:
I was wondering if there's any string that has a hash equal to itself, so that – when using any (none specific) hash function – the hash would be equal to that string?

so that:

hash(x) = x

Note that this is not an assignment or anything. I’m just curious and couldn't find any specific answer or reference. And I’m not sure how to go and prove/disprove that to myself!


texts:
What's the differences between the concepts “pseudorandom generator” and “pseudorandom number generator”?

In fact, I want to implement a pseudorandom function based on GGM's construction at http://crypto.cs.uiuc.edu/wiki/index.php/GGM_PRF, but I need to get a doubling length PRG first. I cannot find any effective way to do this.

Can anybody help me or give me another way to implement a pseudorandom function?


texts:
I am trying to decide whether to encrypt data by using attribute-based encryption or use an encryption algorithm such as AES before using attribute-based encryption.

Is attribute-based encryption used to encrypt data and apply access control, or only do the latter?


texts: Historic Authentication Schemes Before Computers

texts:
The Bulletin of the Atomic Scientists recently ran an article about an alleged near miss with rockets in 1962, which raises some
interesting cryptographic questions:

  After the usual time-check and weather update came the usual string of
  code.  Normally the first portion of the string did not match the
  numbers the crew had.  But on this occasion, the alphanumeric code
  matched, signaling that a special instruction was to follow.

  Bordne’s crew was instantly alarmed and, indeed, the second part,
  for the first time ever, also matched.

  At this point, the launch officer of Bordne's crew, Capt. William
  Bassett, had clearance, to open his pouch.  If the code in the pouch
  matched the third part of the code that had been radioed, the captain
  was instructed to  open an envelope in the pouch that contained
  targeting information and launch keys.

To me it is doubtful that this event ever happened, but it made me wonder how messages were authenticated in pre-computer days during the time of mechanical calculators and long before the advent of public key cryptography.

At this time, the standard was a codebook + superencryption and electromechanical rotor machines. In this case they probably used a code book. Neither scheme provides integrity or authentication.

CBC-MAC as one of the easiest MACs is (barely) feasible to do by hand and doesn't fit the description 'the code in the pouch matched the third part of the message'

Another issue with all of these schemes is that every potential recipient can trivially originate a fraudulent message himself.
There is nothing to keep a rogue crew from opening the secret pouch, constructing a message and sending it out to all other sites.
At that point, all of them will open their pouches, so the seal is useless to find the guilty after the fact.

How were message authentication and integrity handled during the time of codebooks and one time pads? Were there any schemes that provided any non-repudiation capability?

Edit:
I found an article that claims:

  When I served as a Minuteman launch officer in the 1970s, I and
  another crew member could have reverse engineered this entire business
  to create and transmit to the entire U.S. land- and sea-based
  strategic force a fully valid and authentic order that would have been
  carried out by crews whose only validation requirement was to match
  their SAS codes with the order’s SAS codes. (We didn’t use unlock
  codes at the time, even though Defense Secretary McNamara thought
  otherwise). The source of the message was irrelevant; all crews were
  trained to carry out any launch message that validated regardless of
  the source.

But, while somewhat morbidly fascinating, I don't want to dwell solely on the issue of nuclear authentication.
There is a huge body of literature about historical military encryption, but only very little about authentication and integrity. This is strange, because messages were transmitted in error prone Morse code via HF links.
I guess, the famous 'THE WORLD WONDERS' message during the battle of Leyte Gulf shows that at least the Navy did not verify message integrity.


texts: How can I ensure forward secrecy when storing encrypted messages in a public blockchain?

texts:
I want to store encrypted sensitive messages in the blockchain.

I was thinking of using public-key cryptography to achieve this, but as the encrypted data will be stored forever in the blockchain and this data will still be sensitive 100 years from now I am afraid there will be a possibility in the future for people to break the encryption (using quantum computing for example).

Is there a way for me to achieve forward secrecy that will likely not be broken in the near future ?

Thank you

EDIT : I can tolerate a few messages being decrypted in the future (out of the tens of thousands I want to store), but I would like to keep that number as low as possible (less than 0.1%)


texts: How does the random oracle model simplify proofs versus using the standard model?

texts:
If I use the standard model, then the proof must rely on mathematical assumptions.

Will this security proof, generally be longer/more complex?

Is there an example where the random oracle has been used to prove security, then removed to shows this?


texts: Cryptographic hash that supports efficient update after random-access plaintext modification

texts:
Is there a cryptographic hash algorithm that, given the hash of a plaintext, supports supports efficient recomputation of the hash after modifying a single byte of the plaintext?

Specifically, is there a hash function H() such that, given plaintext P and Q of the same length that differ only in the byte at position K, there exists another function R() such that R(P, Q, K, H(P)) = H(Q) and R is O(1)? If so, what are H and R?

Such a function would be interesting because it would allow creating a filesystem that efficiently tracks a cryptographic hash for each of its files. Such a filesystem could be useful for implementing highly efficient file transfer (like rsync) or version control (like git) systems.


texts: Why is it claimed that ElGamal is worse than RSA?

texts:
I have some notes that claim that ElGamal is worse than RSA in the sense that ElGamal is length-increasing. Do anybody know what this means and why is a bad property?

Edit:

For completeness I show you the model of RSA I'm working on (the very basic one)

and also the ElGamal model I'm working on:

In fact ElGamal advantages are also pointed out. First generation of parameters is more efficient and second ElGammal works in various types of groups while the setup for RSA is $\mathbb{Z}_{n}$. So the comparison should be done over $\mathbb{Z}_{n}$.


texts:
I have bought a TPM Chip: SLB9670.
It can be communicated via the SPI Bus.
What is the SPI frame format for firing TPM Commands with or
without arguments. I have read the TPM Main Specifications documents
but haven't found much help. Can someone please help me with this.


texts: Computational indistinguishability: are function parameters known?

texts:
I would like to clarify something about the definition of computational indistinguishability and pseudorandom number generators. Suppose we wanted to show that linear congruential generators of the form $x_t = ax_{t-1} + b \pmod m$ are not pesudorandom number generators. Then we wish to show that given a sequence of numbers $x_0, x_1, \ldots$, we can distinguish whether these numbers came from the lcg process above, or are coming from a uniform distribution (in polynomial time, with high probability, etc...).

In doing so, do we assume that we are given the parameters $a,b$ and $m$? On the one hand, if we are given these parameters, then isn't this trivial? Just check if the given sequence satisfies the given lcg... On the other hand, even if we don't know $a,b,m$, there still clearly does exist a polynomial time algorithm that happens to have $a,b,m$ hard-coded into it that could be used to distinguish these sequences from truly random ones.

What is the correct interpretation here? Does it even make sense to ask whether LCGs are pseudorandom generators in the sense of computational indistinguishability?


texts: Problem related to the discrete logarithm problem

texts: Let $G$ be a generator of a cyclic group in which the discrete logarithm problem is hard and $x$ and $u$ be scalars of the group such that $X = xG$ and $U = uG$, respectively. We want to compute $J = x^{-1}U$. Is it possible to calculate it without knowing $x$, even if we know $u$?


texts: Bounds on failure probability for universal exponent method?

texts:
The following definition is from Trappe and Washington, "Introduction to Cryptography with Coding Theory". Given a number $n$ and an integer $r > 0$ such that $a^r \equiv 1 \pmod{n}$ for all integers $a$ with $\gcd(a,n) = 1$, the universal exponent method attempts to factor $n$ as follows:

Choose a random integer $a$ with $1 < a < n-1$.
If $\gcd(a,n) \neq 1$, return this gcd as a nontrivial factor.
Otherwise, write $r = 2^km$ with $m$ odd, and compute $b_0 \equiv a^m \pmod{n}$. If $b_0 \equiv 1 \pmod{n}$, start over with a different $a$.
Otherwise, repeatedly compute $b_i \equiv {b_{i-1}}^2 \pmod{n}$ for $i=1, \ldots, k$.

If we obtain $b_i \equiv 1 \pmod{n}$ before obtaining any $b_i \equiv -1 \pmod{n}$, stop and return $\gcd(b_{i-1} - 1, n)$ as a nontrivial factor of $n$.
Otherwise, if we obtain $b_i \equiv -1 \pmod{n}$ before reaching any $b_i \equiv 1 \pmod{n}$, start over with a different choice of $a$.

(As a side question, since Trappe and Washington don't give a specific citation for this method, I'd be interested in knowing if there's someone specific I should credit the method to.)

This factorization method is obviously closely related to the Miller--Rabin primality test, and in Miller--Rabin we know that if $n$ is composite, then there is at most a $1/4$ chance of a randomly chosen $a$ failing to prove compositeness.

Assuming again that $n$ is composite, is there any analogous bound for the probability of a randomly chosen $a$ failing to factor $n$ with this method? (What I'm really interested in here, I think, is the worst-case probability over all $r > 0$ satisfying the hypothesis.) I'm not really familiar with the tools used to prove the Miller--Rabin bound, so maybe they give an easy answer to this.


texts: Rijndael - is there some difference in resistance between counter in generator input and in IV?

texts:
I am thinking about Rijndael implementation in order to store tokens (cannot be hashed) - one token for one user. And finally I get stuck with key/IV generation problem :(

The questions are:

1) Is there some difference between the solutions - which is more secure?

2) Do presented solutions have some weak side?

3) Suppose attacker has come to this page and now he knows the algorithm, does it help him a lot to decode passwords?

Solution 1 - counter in generator's input:

Rijndael rijndael = Rijndael.Create()
Rfc2898DeriveBytes pdb = new Rfc2898DeriveBytes(cipherTextBytes + **Counter**, SALT128b, 514);
rijndael.Key = pdb.GetBytes(32);
rijndael.IV = pdb.GetBytes(16);

Solution 2 - counter as IV:

Rijndael rijndael = Rijndael.Create()
Rfc2898DeriveBytes pdb = new Rfc2898DeriveBytes(cipherTextBytes, SALT128b, 514);
rijndael.Key = pdb.GetBytes(32);
rijndael.IV = **Counter**;

Where Counter is unique [0..N] int, cipherTextBytes - the same for every generation byte[200] array.

Both parts have the same end:

MemoryStream memoryStream = new MemoryStream();
CryptoStream cryptoStream = new CryptoStream(memoryStream, rijndael.CreateEncryptor(), CryptoStreamMode.Write);
cryptoStream.Write(passwdByteArray, 0, passwdByteArray.Length);
cryptoStream.Close();

Thank you in advance!


texts:
Recently I'm learning about constructing iO from Matrix Branching Programs via Multi-linear Maps (to be exact, [GGH+13] and [GGH15]). However, I have a small question that I couldn't figure out.
It seems like the steps of converting a program/circuit into an obfuscated one is to first convert it into an MBP (a bunch of $M_{i,b}$s) via [Bar86]. Then, we can use Kilian randomization to add random 2k $R_i, R_i^{-1}$ matrices to make the MBP matrices distribution look random. Next, we put this into the MMap framework that allows people to do add/multiply plus a zero test. Finally, there's some construction that protects input mixing attacks.
My question is that why we need to put this MBP into the MMap framework? It seems like that after the Kilian randomization, the matrices in the MBP already look random and don't leak information. Couldn't we just publish the randomized MBP as the obfuscated version of the program? I feel that I'm missing something here...


texts: I am not sure if Counter Mode (CTR) encryption is mult-CPA (chosen-plaintext attack) secure or not.


texts: Hash collision using the leading 40-bits of SHA-1

texts:
I am trying to implement Floyd's cycle finding algorithm for finding a leading 40-bit hash collision in the SHA-1 algorithm. However, my code will not find a repetition even with 800,000,000 hashes. Can I get some help on this issue?

Here is my code for reference.

REMOVED

Note: I want to understand Floyd's cycle finding algorithm, can someone explain the theory and implementation?

EDIT: Finished Solution
Thanks everyone for the help, It now finds collisions in ~3,000,000 hashes!

#include "sha.h"
#include "cryptlib.h"
#include <cstdlib>
#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
#include <random>
#include <bitset>
#include <time.h>

#pragma comment(lib, "cryptlib.lib")

using namespace std;

CryptoPP::SHA1 SHA;

// takes the reference to a char array and fills it
// with random hex values
void randStr(byte(&src)[5]){
    const char *hex_digits = "0123456789abcdef";
    srand(time(NULL));
    for (int i = 0; i < 5; i++) {
        src[i] = hex_digits[(rand() % 16)];
    }
}

void hash_40(byte (&src)[5], byte (&hash)[5]){
    // Temp hash Storage
    byte k[CryptoPP::SHA1::DIGESTSIZE];
    // SHA Calculation
    SHA.CalculateDigest(k, src, 5);
    // Copy to hash destination
    for (int i = 0; i < 5; i++){
        hash[i] = k[i];
    }
}

// compares 2 strings to length len
// faster than C: strncmp with compiler
// optimizations and works as unsigned
bool cmp_hash(byte(&a)[5], byte(&b)[5], int len){
    for (int i = 0; i < len; ++i){
        if (a[i] != b[i]){
            return false;
        }
    }
    return true;
}

int main(){
    byte
        t[5],
        h[5],
        xT[5],
        xH[5];
    randStr(t);
    copy(begin(t), end(t), begin(h));
    hash_40(t, t);
    hash_40(h, h);
    hash_40(h, h);
    copy(begin(t), end(t), begin(xT));
    copy(begin(h), end(h), begin(xH));
    unsigned long ctr = 0;
    while (true){
        hash_40(t, t);
        hash_40(h, h);
        hash_40(h, h);
        ctr += 3;
        if (cmp_hash(t, h, 5)){
            break;
        }
        if (ctr % 10000 == 0){
            cout << ctr << "\r\n";
        }
        copy(begin(t), end(t), begin(xT));
        copy(begin(h), end(h), begin(xH));
    }

    cout << "\r\n" << xH << "\r\n" << xT << "\r\nHash to the same leading 40 bits\r\n";
    system("pause");
    return 0;
}


texts: questions about sensitivity in differential privacy

texts:
Ted here (What does the term "differential" in "differential privacy" mean?) describes the difference between local and global sensitivity as

"By contrast, local and global sensitivity are only tools to build differentially private mechanisms: they measure how much changing the data of one user will change the output of the statistic you're trying to compute. Global sensitivity measures how big that change can get for every possible database, while local sensitivity measures it for a single database. Local sensitivity is mostly used to define another concept, smooth sensitivity, which in turn is used to design DP mechanisms."

for every possible database, we mean that ones record is to more than one database?

what is more, I see in the definition that local sensitivity takes account only for D'. why not the D as well?


texts: Advantage of AES(Rijndael) over Twofish and Serpent

texts: I'm trying to figure out a suitable encryption technique and after reading a bit, I figured the current AES 128-bit encryption is suitable for what I'm trying to do. However, this is more due to the wide-range use of AES than any other factor. So I need to know how the AES compares to the other finalists Twofish, Serpent of NIST's AES competition in terms of speed, security in software systems.


texts: Solving LPN using algorithm for syndrome decoding

texts:
Given an algorithm $A_D$ which solves an instance of the decoding problem $e \in \mathbb{F}_2^n$ in time $T_D$ given a parity check matrix $H \in \mathbb{F}_2^{(n-k)\times n}$ and a syndrome $s \in \mathbb{F}_2^n$.
You are also given a LPN-oracle with error-probability $\tau$.
Construct an algorithm which solves the LPN-problem with complexity
$\tilde O(T_D)$.
Expanding on this question because of a friendly piece of advice from @kelalaka:
The decoding problem is defined as:

Given the parity check matrix $P \in \mathbb{F}_2^{(n-k)\times n}$, $\omega$ and $x=c+e$ with $c \in C$ and $\mathrm{wt}(e)=\omega$,
find $e \in \mathcal{F}_2^n$.

The LPN is defined as:

Given $x_i \in \mathbb{F}_2^n$, $l_i=\langle x_i,s\rangle+e$, $i \in [m]$, $\Pr[e_i=1]=p$, $p \in [0,1/2)$,
find $s \in \mathcal{F}_2^n$.

My progress:
To be really honest I have trouble understanding the whole topic and because of COVID remote teaching it is really hard to ask for help.
My first idea would be to use $l_i$ as $x$ in the algorithm $A_D$ and construct a fitting parity check matrix in order to get $e_i$ which I can then use to get the value of $\langle x_i,s\rangle$ and since I already know $x_i$ I am now able to extract $s$. But this won't work because I don't think there is a way for finding a unique solution for $s$ knowing $e_i$, $l_i$ and $x_i$.
I think I need to also use the error probability $\tau$, but am too confused right now to think of anything promising.


texts: Differential privacy guarantees of Gaussian noise, when each coordinate has different sensitivity

texts:
Suppose you have a function $f$ that takes a dataset $D$ as input and returns an output in $\mathbb{R}^d$.
If this function has $L^2$-sensitivity $\Delta$, then the analytical Gaussian mechanism (Theorem 8 in this paper) says that if you add Gaussian noise of variance $\sigma^2$ to each coordinate of result, with:
$$ \Phi\left(\frac{\Delta}{2\sigma}-\frac{\epsilon\sigma}{\Delta}\right)-e^\varepsilon\Phi\left(-\frac{\Delta}{2\sigma}-\frac{\epsilon\sigma}{\Delta}\right) \le \delta$$
where $\Phi$ is the Gaussian CDF, then you obtain an $(\varepsilon,\delta)$-differentially private mechanism.
Now, suppose that there is a finer way of describing the sensitivity of $f$. Rather than only knowing a bound on the maximum $L^2$ norm of $f(D_1)-f(D_2)$ for neighboring $D_1$ and $D_2$, we have a per-coordinate sensitivity bound: we know that the first coordinate of $f(D_1)-f(D_2)$ is always below $\Delta_1$ (in absolute value), the second below $\Delta_2$, etc., and $\Delta_d$ bounds the sensitivity along the $d$-th coordinate.
In this case, intuitively, adding the same magnitude of noise along each coordinate doesn't seem like the best solution. For example, if $\Delta_1$ is much smaller than the other per-coordinate sensitivities, then we will likely add too much noise to the first coordinate for it to be useful. Thus my question: is there an equivalent analytical result where we can add Gaussian noise proportional to each coordinate sensitivity?
I know I could be using Laplace noise instead, but then the per-coordinate noise magnitude grows in $O(d)$ instead of $O(\sqrt{d})$ (unless $d$ is sufficiently big to use the Advanced Composition Theorem, but that only makes a big difference for large values of $d$), so I'm interested in a Gaussian noise formula hoping that it will work well for not-too-high values of $d$ (say, $5<d<50$).


texts:
I've been tasked with developing an app that will need to store photos a user takes securely, and I've been struggling to think up a method to do this.
What I was thinking so far is as follows:

When user first logs into the application, input their password along with a salt (stored in a database) to a key-derivation function to generate a hash
Use this hash to encrypt an AES key
Store this on a database

This way, when a user logs into the app, they can request the encrypted AES key and decrypt it by producing the same hash produced from their password.
Using this AES key, they can encrypt photos before sending them to the server, and decrypt them upon receiving them back.
Is this a viable method? Is there a better way to do it?
Any help would be appreciated.


texts: Why is 2PC not used as any other primitive like DH?

texts:
Why is 2PC (2-Party Computation) not used as any other primitive like Diffie-Hellman?

I'm not talking about the general secure computing, but some weaker security requirement or special case schemes.

A number of tricky methods for GC (Garbled Circuit) have been proposed like free-XOR, half-gate and so on. And recent promotions like TinyGarble, LEGO seem practical.

Is there any irreplaceable need for such primitives in the real world? Or is the GC the only way for MPC (Multi-Party Computation)?


texts: Triple DES as cryptographic hash function

texts:
I need to generate a hash for a small piece of data (~50 bytes). I'd normally use MD5 or SHA but that's not available in the platform I'm programming for.

Luckily, it provides Triple DES and I thought I could use it as cryptographic hash function (pseudo-code):

function MyHash(text)
    data = padded(text, 64)
    key = data[0:8] + data[8:16] + data[16:24]
    encrypted = TripleDES(data, key)
    return encrypted[0:16]

MyHash will produce 128-bit (16-bytes) long hashes for input text.

Is MyHash secure? How does it compare with MD5 and SHA-*?


texts: Does ChaCha20-Poly1305 need random nonce?

texts:
RFC 7539 says:

  A 96-bit nonce -- different for each invocation with the same key

It doesn't explicitly say whether it has to be random or not. If we use an ever incrementing counter. Would that be secured? Generating cryptographically secured random number is a slow process.


texts: How do I create a short signature? (e.g. less than 100 bytes)

texts:
I want to put information into a QR code and have it signed so that the authenticity of the information can be verified. But QR codes have limited storage capacity and when I used e.g. gpg I get signatures typically about 500 bytes long.

For this application it is acceptable to trade some security for both space and convenience.

It would be preferable if there is a way of doing this that can be done with standard or easily obtainable tools such as gpg, openssl or similar.


texts: What can be deduced/extracted from this local hash extracted from Windows Machine?

texts:
I'm new to cryptography. I've been experimenting with getting Windows hashes to see whether it's possible to reverse engineer. The following hash is what I got from my test laptop. What can you identify here and what is possible to do with this kind of hash. However, I'm not solely interested in extracting the password, but truly understanding which types of hashes are being used here.
I've extracted this hash by using a program called Lazagne.
Hash:
$$DPAPImk$2*1*S-1-5-21-3135680238-1618761808-2876590207-1001*aes256*sha512*8000*af87ccc856973aca8457d0a215ba71fd*288*e97a8bd1c9281cb7544ae53a3bd0e181dd9bc49f4bd6733d1226bce4b955a88a94b6938ca0e48bdcffdb59cec1ab98b17bef4d9ca87af21b6ea4ce52f781211912628813a9a50766afbedc4e3549412b9dab65ffd0db5458201887171b5053458afe04f20a30e2de3db60eba2f29291aac55f0e05f8f7c852f8434a907c87ded9d09e2832772a894a8a029ff1541a742


texts:
Given a short Weierstrass elliptic curve $C$ over $F_p$ and a point $(x, y)$, it is easy to verify that $(x, y)$ either satisfies the curve equation (on-curve) or does not (off-curve).

In the case that it is off-curve, is there an efficient way to test if $(x, y)$ is on a quadratic twist of the curve? I can easily generate domain parameters $a, b$ of a twisted curve $C'$, but unless I have the correct coefficients, $(x, y)$ might not satisfy that particular curve equation $C'$ even though $(x, y)$ are on a twist of $C$.


texts: Security of this deterministic encryption scheme

texts:
I recently came across a library that promises to do deterministic encryption with the following scheme:

  AES with 256 bit key in CBC mode with PKCS7 padding and Synthetic Initialization vector taken from the first 16 bytes of the HMACSHA256 mac of the plaintext. I use the same key for confidentiality and integrity. Ciphertext is Base64Encode( MSB(128, mac(k, plaintext)) || E(iv, k, plaintext) ) where MSB(b, v) stands for the b most significant bits (left-most) of v.

My question is: does this scheme have any security flaws? How would it compare, for example, with using SIV mode as described in RFC 5297? Specifically, does it provide the same guarantee for message authentication and integrity?


texts: Salsa20 Implementation: Sum of 2 Words with Carries Suppressed

texts:
I'm working on the 2nd part of the Salsa20 spec, and I want to implement a closure for the exclusive-or of two words(u32). The author defines the operation as the sum of two words with carries suppressed, but what does "carries suppressed" mean? Then I come across some summation notation:
$u=\sum_i2^iu_i$
What does the variable "i" mean in this context exactly? I understand summation notation and the index variable, but the context of the spec doesn't elaborate enough for me to know what "i" indexes.
I realize this all may be very rudimentary, but I am a programmer first.


texts: How to use separate keys for signing and encryption

texts:
I read that the same key should not be used for both certificate signing and encryption.

I wonder if this is not a problem with PKI/TLS/SSL, the reason being asymmetric encryption is used to transmit the public key (via the certificate).  The public key is used to encrypt a browser generated session key.  The session key is used for symmetric encryption of the actual traffic.

Is that how it works and does that mean it is okay to sign both with the same key?

How would I go about using separate keys?


texts: When to use /dev/random over /dev/urandom in Linux

texts:
In my response to my question "what does the letter 'u' mean in /dev/urandom?" the myths about /dev/urandom
page was posted in two comments and an answer.

The myths about /dev/urandom page is trying to steer people heavily into using /dev/urandom over dev/random.

This guy knows more than I do, so it would be easy for me to nod and accept, but I'd like to post it here so that other people who also know more than I do could comment.

What irks me about myths about /dev/urandom is that:

The two devices still have a differing behaviour depending on the size of the entropy pool
There are no use cases given where /dev/random is the better choice (which seems unbalanced)

I note that cryptsetup has an option --use-random:

  NOTES ON RANDOM NUMBER GENERATORS

  Using /dev/random on  a  system  without  enough
         entropy  sources  can  cause  luksFormat  to  block until the requested
         amount of random data is gathered. In a low-entropy situation (embedded
         system), this can take a very long time and potentially forever. At the
         same time, using /dev/urandom in a low-entropy situation  will  produce
         low-quality  keys.  This is a serious problem, but solving it is out of
         scope for a mere man-page.  See urandom(4) for more information.

So my question is:

In which practical situations would one want to use /dev/random in preference to /dev/urandom, and why?


texts: Structure for an introductory course on cryptography?

texts:
Many introductory courses on cryptography have their treatment of secret-key crypto start with OTP, then block ciphers, and for public-key cryptography revolve around RSA with no notion of padding (some even have matching exercises showcasing insecure practices, beyond using artificially small parameters). It is all too common that after such introductory course, students will happily consider the OTP as a useful cipher, or tell (and try to perform) things like encrypt with private key, and believe (perhaps rightly) that's what they have been taught.

I ask what would be a better roadmap for a short introductory course on cryptography, aimed at students with an inclination towards engineering and IT, that

gives the audience a fair grasp at the basic functions modern cryptography performs routinely (signature, authentication, key exchange, encryption..), and how they differ in goal;
illustrates some of these functions with concrete methods, not requiring much more advanced math than RSA does, and implementable (with artificially small parameters) on about anything that can compute, including spreadsheet formulas;
not touching formal definitions of security, much less game proofs, advanced cryptanalysis..

I realize that an actual course content will depend considerably on the time allocation, math background of the audience, and the (widely varying) organization and goals of the learning environment. I wish these things are left out inasmuch as possible, to concentrate on what cryptographic techniques should be in a coherent exposition of cryptography, so that this question can hopefully be considered on-topic.


texts: Kryptos : K2. What is the origin of the “abscissa” keyword?

texts:
I'm studying the Kryptos sculpture with its cryptographic puzzles K1 to K4.

Similar to the "palimsest" keyword for K1, the keyword "abscissa" for K2 was determined by brute-force.

To better understand the puzzle as a whole and ultimately solve K4, it's important to understand how the "agent in the field" might have discovered these keywords.

One suggestion is that the keyword "abscissa" is derived from the plaintext of K1 which reads:

  BETWEEN SUBTLE SHADING AND THE ABSENCE OF LIGHT LIES THE NUANCE OF IQLUSION

Which, given a sort of "cryptic crossword" reading can give you:

Between "Subtle Shading And" -> "SSA"
... the ABSence -> "ABS"
... of Light (speed of light == "C" in physics) -> "C"
... lies the nuance of Iqlusion -> "I"

And with standard sort of anagram "fun", one comes up with "ABSCISSA."

Not very strong, but maybe believable.

Is there a better theory out there?


texts: SHA-1 collisions - what about practical attacks?

texts:
I understand the theoretical problem with hash collision but when it comes to practice, I get very confused.

Suppose a attacker would like to forge a certificate (or any kind of structured piece of file) using hash collisions, I wonder how it is possible to find a collision (already unlikely) and moreover, this collision is "found" from relevant structured input bytes (dates, common name, dns attacker).

It sounds very strange for me, I can't understand how one can found a hash collision which helps as an attack, I can only think about a random raw bytes which could generate a same hash, but it would not be parsed (ex: x509 certificate hash collision find by an attacker, but the x509 malicious content is random bytes not understandable by browser).


texts: Why does DH-EKE require that public keys be indistinguishable from random?

texts:
The introduction to SPAKE pre-authentication states:

  Diffie-Hellman Encrypted Key Exchange (DH-EKE) is the earliest widely deployed PAKE. It works by encrypting the public keys of a Diffie-Hellman key exchange with a shared secret. However, it requires both that unauthenticated encryption be used and that the public keys be indistinguishable from random data. This last requirement makes it impossible to use this form of PAKE with elliptic curve cryptography. For these reasons, DH-EKE is not a good fit.

I'm curious about the sentence in bold--why does DH-EKE require that the public keys be indistinguishable from random data? After all, the public keys are public, and furthermore, they will be encrypted with the shared password.

I'm guessing that if the public keys are in fact distinguishable from random data, that that reveals some information about the shared password, but I don't know how.


texts: DES: Initial permutation position decreases by 8 - what is the significance?

texts:
I'm a beginner in the complex world of cryptography. Doing some basic course on DES, and I found a peculiar (to me) pattern within DES' Initial Permutation table.

The table is built as an 8x8 matrix with shift position: https://en.wikipedia.org/wiki/DES_supplementary_material#Initial_permutation_.28IP.29

The pattern graphically presented on the wiki page happens to decrease by 8 in every row. What's also interesting, is that the values between neighbouring rows, but different columns seem to differ by 2.

This may be "just randomly selected", but assuming that DES has been thoroughly designed, implemented and - most importantly - tested, this seems on purpose. Hence: What is the significance of the pattern within IP?

(my wild guess is that it's of rather little importance, as IP is easily reversible)


texts: How to implement the Salsa20 hash function?

texts:
I am currently implementing Salsa20 from the specification as an exercise in learning and self-flagellation.

I have Sections 1-7 passing the test examples provided. I am now stuck on Section 8, The Salsa20 hash function (Page 6):

1) What is confusing is the doubleround$^1$$^0$. What does this mean exactly? Perform the doubleround function $10$ times on the $x$ words from earlier? I.e. I perform doubleround($x$) once, then feed the result of that back into the doubleround function again, then repeat that 8 more times?

2) After that it does a littleendian$^-$$^1$($z0 + x0$). I know what the littleendian function is as it was defined previously in Section 7. But what is littleendian$^-$$^1$? The inverse of it? Do I simply pass the result of the $z0$ and $x0$ addition back into the normal littleendian function again (which as a byproduct would reverse the results of the littleendian function)?

3) To produce the final output, do I concatenate the 16 words (4 bytes per word) from the littleendian$^-$$^1$ function together, then convert them to bytes to get the resulting 64-byte sequence?

Perhaps some psuedo code would answer these questions more succinctly.

Gracias amigos.


texts: Is there a way of increasing the time to brute force a cipher, but by increasing the ciphertext size instead of the key size?

texts:
If you have a symmetric-key algorithm that is limited to using a small key size (say 40-bits) is there any way you could increase the resistance to brute force attacks without increasing the key size?

I am interested in approaches that increase the ciphertext message size (such as padding of some form, or a method that creates a ciphertext larger than the plain text) as I think it would still be affordable to transmit a message that is up to 10 times the original plain text size.

Is there a way to greatly increase the time a brute force attack would require to decrypt the message without increasing the key size?

For prior art I can provide this paper about hiding the key in large amount of random data, and the Chaffing and winnowing method that word plays with authentication and encryption.

Later I found this paper that asks "Is there any way to significantly increase the difficulty for an adversary of performing a brute-force search, while keeping the key size the same and not overly burdening the legitimate communicants?", which is the question I am asking.


texts: Can all asymmetric key pairs be reversed?

texts:
After reading about public/private key cryptography, there are still a few points I don't really understand.

Based on the way (I understand) challenges work, the public key is used to encrypt a sequence which the private key can be used to decrypt:

When a key pair is freshly generated, does it matter which key that is chosen as the private key since the opposite key can be used for encryption?
Does this apply to all known and/or hypothetic asymmetric encryption algorithms?


texts:
Modern stream ciphers usually predicts the usage of a nonce (also termed as IV) in the cryptosystem. The cost of initializing the cipher with the nonce varies from algorithm to algorithm (for instance, this cost seems very high on HC-256 and negligible on Salsa 20). I would like to know the correct usage pattern of a nonce together with the stream cipher in a cryptosystem. The only thing I know for sure is that they must never repeat...

Does it needs to be new for every transmitted message?
It must be secret? (Is it assumed to be known by an attacker)?


texts:
Intro
I am somewhat new to cryptography.
Repeating the basics of RSA from How are the primes used to generate RSA keys?:

Textbooks say the one-way function is merely two primes (with some
critical constraints) ...

may be a good base of this question, as well as What prime lengths are used for RSA?. Also, Big data and modern crypto systems already asks the same thing as the question here, but in a more abstract way.
The idea
Why not calculating in advance, on many computers, a vast amount of multiplications of primes that you loop over systematically, in the constraints of RSA? And then you would save the outcome as keys in a Big Data system that you can quickly search through? You could use a Bloom filter, a key coordinator or other Big Data tricks to quickly find the computers that might have the multiplied value at hand, and then quickly find a value's underlying primes.
You could have 10000 computers, with chosen different starting prime ranges. The first and second primes could be within a likely range that is needed to meet RSA standards of 4096 bit. You may also guess a bit, meaning to take a range that is rather around the square root of a chosen outcome, or take other tricks to guess a bit.
Then it just depends on how many computers you use. Even if you hit just 0.001 % of the possible combinations you could already get the private key from the public key in 0.001 % of the cases. Or do I oversee something here.
The question
It cannot be that easy, can it? Can Big Data attack RSA by just calculating many prime multiplications in advance?


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

texts:
Wang's (et al) differential attack works on MD5, MD4, RIPEMD and HAVAL.

Why doesn't it work on SHA-1?


texts: How is injective, inverse, surjective & oneway related to cryptography?

texts:
Just researching cryptography concepts and finding it really hard to absorb them. I would love to know how these functions (injective, inverse, surjective & oneway) are related to cryptography.

Note that  I am just looking for a brief answer. Something that makes sense to someone researching Crypto for the first time. I surely don’t expect a full-fledged (too broad) explanation.


texts: For most applications of CMS, does the size of the payloads ever exceed that of a 32-bit integer?

texts:
For my hobby cryptography project, I'm planning to implement some helper functions that parses a subset of ASN.1 BER encoding without using a ASN.1 compiler. For this purpose, I'd like to use 32-bit integer for the internal representation of tags' and lengths' values.
If I were to extend my library to other application domains such as CMS (cryptographic message syntax), should I prepare to extend my type to 64-bit?


texts: Prove that function G is not a pseudo-random generator

texts:
I'm trying to do the following assignment:

  Let $G:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$ and $G':\{0,1\}^n \rightarrow \{0,1\}^{n+2}$ be two pseudorandom generators. Prove
  that the function $G'':\{0,1\}^n \xrightarrow{}\{0,1\}^{2n+3}$ defined
  by $$G''(s_1, \dots, s_n) = (G(s_1,\dots,s_n),G'(G(s_1,\dots,s_n)))$$
  is not a pseudorandom generator.

I know that despite $G$ and $G'$ are pseudorandom functions, the way in which they
are combined makes the new function vulnerable. Letting $G''(s_1,\dots, s_n) = (y_1, \dots, y_{2n+3})$ is possible to create $(y_{n+2}, \dots, y_{2n+3})$ from $(y_1, \dots, y_{n+1})$. I think it's possible to crete a distinguisher that exploits this fact, but I don't know how to prove it.

Any help about how to move on?


texts:
We already have recommendations on what PQCrypto to use:
PDF (page 11)

  Symmetric encryption Thoroughly analyzed, 256-bit keys:

  AES-256
  Salsa20 with a 256-bit key

  Symmetric authentication Information-theoretic MACs:

  GCM using a 96-bit nonce and a 128-bit authenticator
  Poly1305

  Public-key encryption McEliece with binary Goppa codes:

  length n = 6960, dimension k = 5413, t = 119 errors

  Public-key signatures Hash-based (minimal assumptions):

  XMSS with any of the parameters specified in CFRG draft
  SPHINCS-256

What would it cost to upgrade to those recommendations?

We assume that the recommendations will survive further scrutiny and that upgrading software is for free. In practice it will happen as part of a software upgrade that will happen anyway.

What is the additional:

Disk usage
RAM usage
CPU usage
Bandwidth usage

for a normal user and for a normal website?

Since users mostly visit the same websites as they did the day before I am thinking that the key exchange may not be so scary after all. If the SSL certificate is only downloaded every few months, then it will be very little extra bandwidth.


texts: Given occasional LFSR samples can the next sample be computed?

texts:
Suppose I have access to an LFSR generator output used in a radio communications system, with the LFSR being used to authenticate devices. The system cycles an internal unknown length LFSR (greater than 32 bits) an unknown but constant number of times and returns the truncated upper 32 bits, with the lower bits being unknown.

I do not know the starting condition or the polynomial, but I can read the truncated output from this system as it transmits. Using this data alone, can I predict the next output using an algorithm such as Berlekamp-Massey algorithm?

I know that Berlekamp-Massey can solve given 2n captured bits, but do these have to be completely consecutive, or can they be a scattered "picture" of the output? Do I need to know the size of the generator to use Berlekamp-Massey?

I'm thinking of implementing this in a communications system: power consumption and complexity is key here, and an LFSR uses considerably less power and flash memory than a full AES or SHA authentication system, but I'm not sure if it will be easy to predict. (The idea is the receiver will refuse to acknowledge packets an incorrect LFSR, preventing the device being "impersonated".)


texts: Padding in Keccak SHA3 hashing algorithm

texts:
In FIPS-202 specification, the padding required for SHA3 were not clearly mentioned. so we have analyzed the NIST test vectors for SHA3, which states that append "0x06" (never used 1 followed by 'j'zeros and then 1 specified in FIPS-202) to the message digest, which is a contradiction to the specification.

The link for NIST test vector is :-

http://csrc.nist.gov/groups/ST/toolkit/examples.html#aHashing

http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/SHA3-224_Msg0.pdf

could you clarify padding mechanism  for SHA3?


texts: How to use Frobenius for finding Square Roots in $GF(2^m)$

texts:
Given a polynomial $x$ with degree $n$ in $GF(2^m)$, $1 < n < m$, will any generator of $GF(2^m)$ suffice when applying the Frobenius automorphism to determine the square root of $x$ as described in the answer to this related question?  And why? (anecdote or rigid proof are both welcome).

For example, given $f(x) = x^2 + 1$

By trial and error, $x^{2^{n-1}}$ with generators $x^{257} + x^{12} + 1$ and $x^3 + x + 1$, both yield $x + 1$.

Of course, for an efficient algorithm, the smaller the degree, the faster the $x^{2^{n-1}}$ computation.  But computing a generator for every degree that might be needed (or as needed) would be daunting.  Instead, and assuming one can rely upon the general case, i.e., "any primitive generator having degree greater than that of $x$ will do", one can use a table from a source like this (A Table of Primitive Binary Polynomials - M. Zivkovic et al).

I am very new to finite fields and haven't got all the terminology much less the understanding correct, so I hope the example clarifies my question.

EDIT: Background

Consider the Galios relationship:  $S_j = S_0 x^j mod P$, where S, x, and P are all polynomials with coefficients in GF(2).  $P$ is not irreducible in this case.  So, to determine the period of $P$, it must be factored, and by finding the derivative of $P$ to be 0, we know a square exists.  The referenced answer says that by the Frobenius automorphism, the square root of a polynomial is $x^{2^{n-1}}$.  But in this case, $n$ and an $r(t)$ are not given.  Can they be chosen specially for the case of $P$?  For instance, can $n$ be set to $degree(P) + 1$ and can $r(t)$ be chosen with $degree(n)$ from a table of known irreducibles?


texts: Provable Security: concrete approach vs asymptotic approach

texts:
I was reading Professor Lindell and Katz's book. Their book takes the asymptotic approach to the security proof, while lots of papers on crypto seems to use the concrete approach when it comes to security proof.

Are there any references/books that use the concrete approach in their proofs?


texts:
I have two questions here.

What does the cipher-text overhead means?
Why we were suggested not to encrypts the plain-text itself instead just encrypts only the key (i.e random number)


texts: Would this prevent FNV1a 32 bit hash collision?

texts:
I am considering the FNV1a 32 bit hash as part of a simple software security and authentication system. I am aware that FNV1a is NOT ideal but it may suit my needs.

I am aware that FNV1a has rather poor collision behavior, but I would like to know if it may be implemented in such a way as to minimize problems. Assuming pass-phrases are hashed in their entirety multiple inputs may have the same output, but what if each character of a pass-phrase is hashed and the hashes are concatenated in a string?

I suppose my questions is, is collision less likely for individual characters than for strings?


texts: What is meant by - computational complexity $2^x$?

texts:
Recently Bi-clique Cryptanalysis allowed to obtain following results on full AES ES that claim to have

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}$

What is meant by $2^{126.1}, 2^{189.7}, 2^{254.4}, ...$ and if I happen to create a crypto algorithm on my own (which I know is not a good idea) how can I measure it's strength?


texts: Could anyone explain how secure is bit level permutation? What is the most serious threat against the security of this kind of cipher?


texts: Proof of $\sqrt{\pi/2}$ in birthday paradox?

texts: I had found in the past a publication in a crypto conference (in 80s if i am not mistaken) which I believe was the first proof why for example a random function $f:X\rightarrow X$ with $\#X=2^n,$ is expected to have collision in $\sqrt{\frac{\pi}{2}\times 2^n}$ iterations. I can't find it, anyone has the reference?


texts: What are the best practice, and standard tools for blinding algorithms?

texts:
I'm developing an app that uses blind signatures. I'm having a hard time finding tools, and best practices for blinding. There is no PKCS. And everywhere I go, I find caveats of different blind signature schemes.

I've read mixed things about RSA blinding, and looked at this RSA blinding algorithm. But it doesn't seem to have any users. https://github.com/cryptoballot/rsablind

I also found this ECC example which uses the bitcoin curve. But it isn't idiomatic go code, and has no users.
https://github.com/mndrix/btcutil/blob/master/examples/blind/blind.go

In my app, Alice blinds her public key, and gets it signed by a signing authority, the unblinds it. She later signs documents with her private key. Observers check Alice's document signature with her public key, and they check that Alice's public key is signed by the signing authority. The signing authority should not be able to associate blind messages it has signed to unblinded signatures.


texts: Find Lower bound on key space with relaxed definiton of perfect secrecy

texts:
Consider a relaxed definition of security. Let $\epsilon < 1$ be a constant and say we only require that for any distribution over $M$ ,any $m \in M $, and any $ c \in C$

$$
|Pr[M=m|C=c] - Pr[M=m]| < \epsilon
$$

I want to find a lower bound on the size of key space $K$ relative to $M$ for any encryption scheme that meets this definition.


texts: parameter choosing for SIS based scheme in lattice based cryptography

texts:
In SIS based scheme, there is a  matrix  $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}$, and $n$ is the security parameter. I want to ask that why $n=1$ is also okay for the scheme (in "A framework for building composable zero-knowledge proofs" the authors choose the following parameters for the Ajtai hash function, see the following picture). At this time, the security of the Ajtai hash function is based on the SVP problem with dimension 1.

Is SVP with $n=1$  hard?
And n is a small positive integer is also OK  for SIS based scheme in lattice-based cryptography?

I also see that "$n = 1024$, which is a typical choice for lattice-based schemes targeting medium or high-security levels" in the paper "Blaze: practical lattice-based blind signature for privacy-preserving application".

So how to explain this? I say that why there is a preference choosing for $n$？


texts:
Is there any consensus (i.e. are there any research results) on the benefits and drawbacks of various padding schemes?

Generally there seem to be two kinds of them:

random paddings, like ISO10126 that pad with random data
fixed paddings, like PKCS5/7 and X.923 that pad with 0s or some fixed pattern

Is there any reason to prefer one over the other?

In another question of mine it was mentioned that random paddings may be susceptible to subliminal messages, but that answer doesn't cover paddings in general.


texts: Why do PKI schemes need security proofs?

texts:
When it comes to designing new PKI-based key-exchange protocols, why are security proofs needed?

Without them, can we show a protocol's security? Does there exist a PKI-based key-exchange protocol that is secure without a security proof?


texts: Would it be possible to generate the original data from a SHA-512 checksum?

texts:
So, I have a file that is XY Exabytes big. I create a SHA-512 hash from it.

Are there any theoretical chances that I can retrieve the original data just from the sha512 hash?

Also, are there any better hashes then sha512?


texts:
Say that X is a (k; n)-source if $X\in\{0,1\}^2$, and the min-entropy of X is at least k.
Answer the following questions:
(i) Suppose that $l=128$; what is the minimal amount of min-entropy needed
in order to obtain statistical error $\epsilon=2^{-80}$ when applying the leftover hash lemma? What is the entropy loss?
(ii) Suppose that $k = 238$; what is the maximal amount of uniform randomness that you can obtain with statistical error $\epsilon= 2^{-80}$ when applying the leftover hash lemma? Explain how to obtain $l= 320$ using computational assumptions.
I tried to solve this problem applying the LHL, but I'm not so sure.
For the first problem I used that $l=k-2log(\frac{1}{\epsilon})$, so I found $k=288$. But for the other questions I have no idea.


texts:
Whenever I look at online voting schemes, the idea of homomorphic encryption being a key concept, specially in the form of homomorphic tallying, appears to be universally accepted. The accepted answer for this question, for instance, suggests that it is one of the two most important technical approaches to online voting (the other one being mixnets).

The general approach for homomorphic tallying that I have found so far (supported on different additively homomorphic encryption schemes) is to define the tally as a single number, assigning some bits to the part of the tally corresponding to each voter. For instance, assuming that we have 4 voters and 3 candidates, the tally can be represented by the bit string ABCDEF, such that the candidate 1 has AB votes, the candidate 2 CD votes and the candidate 3 EF votes. In the general case, getting the values for each candidate given the integer representing the tally should be a trivial set of bit operations.

The problem is that it doesn't seem to scale: if I had 50 candidates and 256 voters, I'd need a tally of size 8*50=400 bits. It is my understanding that homomorphic schemes and big integers are not a very efficient combination. However, I cannot find a scenario that addresses this problem and shows that it is feasible in a country wide scenario (where voters can be hundreds of thousands, or even millions, and candidates can get up to a few hundreds), or, quite the opposite, clearly states the practical limits of homomorphic tallying.

Am I missing something? Is homomorphic tallying as restricted as it seems? If so, why is it regarded so highly as a building block for online voting?


texts: Known Plaintext Attack for Modified OFB Mode of Operation

texts:
Question: Assume a variant of the OFB mode by which we only feedback the 8 most significant bits of the cipher output. We use AES and fill the remaining 120 input bits to the cipher with 0's:

Why is this scheme weak, if we encrypt moderately large blocks of plaintexts, say 100-KByte? What is the maximum number of known plaintexts an attacker needs to completely break the scheme?
Let the feedback byte be denoted FB. Does the scheme become cryptographically stronger if we feedback the 128-bit value $FB,FB,FB,\ldots,FB$ to the input (i.e.) copy the feedback byte 16 times and use it as AES input?

Solution:

The problem with the scheme is that there are only 256 different inputs $FB_i$ to the AES algorithm. That means there are only 256 different output vectors of length 128 bit that form the keystream. To make things worse, the cipher output will run into cycle quickly. Let's denote the sequence of feedback bytes by $FB_1,FB_2,\ldots$ As soon as the feedback byte $FB_j$ is generated that is equal to an earlier one $FB_i$, i.e. $i<j$, the sequence;$$FB_i,FB_{i+1},FB{i+2},\ldots,FB_j=FB_i,FB_{i+1},\ldots$$
Repeats periodically. Since there are only 256 different values for $FB$, the maximum sequence length is 256. Since each value is associated with a 128 bit (16-byte) AES output, the keystream sequence $s_i$ has a maximum cycle length of:

128x16= 2048 byte= 2kbyte. ( Isn't that wrong? Should be 256x16 in my opinion? )

After this, the stream cipher output must repeat(and odds are that the cycle length is much shorter). Thus if an attacker has to know at most 2 kbyte of plaintext in order to recover the entire system stream cipher output with which he can decrypt all other ciphertexts.
No, we still only generate a maximum of 256 keystream words of length 16 byte.

This solution is from the manual of the book. I did not get why it is 128x 16 insteaf of 256x 16 in  part 1? Can anyone explain it to me. Also i did not get the part 2 at all. I need a comprehensive explanation.


texts: Why does the update algorithm of HMAC_DRBG use two rounds?

texts:
I read this paper, which said that $\operatorname{update}(K, V, adin)$ should do two rounds as follows:

$\operatorname{update}(K, V , adin)$:

$K = H(K, V || 0x00 || adin)$
$V = H(K, V )$
If $adin = null$, then return $(K, V )$
$K = H(K, V || 0x01 || adin)$
$V = H(K, V )$
Return $(K, V )$

Why is the second round ($K = H(K, V || 0x01 || adin)$) necessary in the case where $adin$ is attacker-controlled? Since the attacker doesn't know the initial value of $K$, shouldn't the new value of $K$ as $H(K, V || 0x00 || adin)$ be unpredictable to the attacker?


texts: Are there any practical implementation of a homomorphic hashing or signature scheme?

texts:
A homomorphic hash function is a function $H : A \to B$ between two sets with some algebraic structure $(A, *)$ and $(B, \star)$ such that

$H$ is collision resistant, i.e. it is hard to find $x \neq y$ such that $H(x) = H(y)$ and
$H$ is a homomorphism, i.e. $H(x * y) = H(x) \star H(y)$.

Are there any practical realizations of such a homomorphic hash function, or even a homomorphic signature scheme (i.e., where we can "add" valid signatures to get a signature of the "sum" of two messages)?

Even better, are there even any libraries implementing this?


texts: will HMAC survive Grover algorithm ? if not then which MAC scheme provide post-quantum security ?


texts: How reassuring is CRC-then-XTS as authenticated encryption?

texts:
It is known that the "xz" compression format embeds a checksum in the compressed file to verify integrity during decompression or standalone testing. The algorithm of the checksum can be one of: CRC32, CRC64, and SHA256, and the default is CRC64.

Now, we put an "xz" file into a XTS-encrypted disk image. The XTS mode is a pure confidentiality mode, and have no authenticity or integrity feature at all. But the "xz" file inside it has integrity feature. So the question is:

When combining the CRC64 integrity of "xz" with the confidentiality of XTS mode of operation, do we get a secure deterministic authenticated encryption (DAE, a.k.a. key-wrap) scheme?


texts: Is it possible to perform CPA(Correlation Power Analysis) when attacker has only specific round's waveform?

texts:
I read Quite a lot document about breaking AES using CPA.

But most of them, assuming that attacker has the first or last round of the waveform(trace) and exploit SubBytes.

My question is if the AES-128 (or AES-256) can be attacked even if attacker has only a certain round of waveform, not the first and last.

Even if attacker has the multiple pairs of plaintext and ciphertext, Is it impossible to figure out the encryption key using only a specific round's waveform?


texts: Difference between server salt and client salt?

texts: Basically I am trying to understand the difference between server salt and client salt. I know that the client salt is used to make encryption harder for hackers, but I can't seem to grasp the concept of a server salt. Does anyone know?


texts: Side-channel attacks against ECDH for Weierstrass normal form curves

texts:
I hear a lot about why Montgomery curves are used in ECC, and one reason is that the same algorithm can be used to do both point addition and doubling (this is not true for the Weierstrass normal form).

What are the most prominent unsafe features of curves, and ways one can screw up an ECDH implementation? Are there "more" ways to screw up with the WNF as opposed to the Montgomery form?

Can you point me to an overview of the problems associated with curves in WNF?


texts: Can Elliptic curve Diffie–Hellman (ECDH) shared secret be used as a static encryption key?

texts:
I have two parties:

Alice who has a static public key PA

Bob who has a static public key PB

A static shared secret (S) is computed with ECDH.

Encryption and MAC keys are computed with a key derivation function:  (KENC, KMAC) = KDF(S)

The two parties send messages to each other, encrypted and authenticated respectively using KENC and KMAC. The encrypted messages are also stored in this encrypted form.

My question: how secure is using these static derived keys (KENC and KMAC) in the long run if I want encryption and authenticity, but I do not care about forward secrecy.


texts: Security of a signature scheme based on both factoring and discrete logarithms

texts:
I have seen this paper: A New Signature Scheme Based on Multiple Hard Number Theoretic Problems by Ismail and Tahat:

  In this paper, we propose a new signature scheme based on two hard number theoretic problems, factoring and discrete logarithms.

It seems that it is a dramatically more secure signature scheme.
Looking for thoughts/insights as to how useful/safe it actually is.


texts: ElGamal: Multiplicative cyclic group and key generation

texts:
Here on the ElGamal wikipedia page http://en.wikipedia.org/wiki/ElGamal_encryption

  Alice generates an efficient description of a multiplicative cyclic group G, of order q, with generator g.

How is this done?  What are some of the properties here?


texts:
I'm having trouble finding the first paper that introduced the $q$-Strong Bilinear Diffie-Hellman ($q$-SBDH) assumption which, roughly speaking, is:

Let $\mathbb{G},\mathbb{G}_T$ be two groups of order $p$, with a bilinear map $e$ from $\mathbb{G}$ to $\mathbb{G}_T$.
Let $s \stackrel{$}{\leftarrow} \mathbb{Z}^*_p$ be a trapdoor. Given $pp = \langle g, g^s, g^{s^2},..., g^{s^q} \rangle \in  \mathbb{G}^{q+1}$, an adversary has negligible probability of finding $\langle c, e(g, g)^{\frac{1}{s+c}} \rangle$ for some $c \in \mathbb{Z_p} \setminus \{-s\}$.

Some papers seem to point to Dan Boneh's "Short signatures without random oracles and the SDH assumption in bilinear groups" (Journal of Cryptography, 2008). However, as far as I've read the paper, only $q$-SDH is defined there, not $q$-SBDH.

Any help would be appreciated!


texts: secretKey ⊕ (secretKey ≪ 1), is randomness lost?

texts:
A truly random secret key is run through a cipher

secretKey ⊕ (secretKey  ≪ 1)

is randomness lost? As in, is the computational cost to guess the ciphertext from secretKey ⊕ (secretKey << 1) lower than the cost to guess secretKey?


texts: Do any other factors aside from length of input affect the runtime of the SHA-256 hashing algorithm?

texts:
To my understanding, the only factor that (even if ever so slightly on most implementations) affects the run time of SHA-256 is the amount of padded chunks the extension & compression function have to run over. The only way to alter the amount of padded chunks is to change the length of the input. Therefore, the only factor influencing the runtime of SHA-256 is the length of payload to be hashed. Is this correct, or are there further aspects that influence the runtime of SHA-256?
Edit: To clarify, this question is talking about the abstract runtime / the runtime on one particular implementation


texts: Guessing the Secret in RLWE Search-to-Decision

texts: In On Ideal Lattices and Learning with Errors over Rings, the authors prove a search-to-decision reduction by guessing the RLWE secret $s$, and using the guess to transform a sample from $\mathfrak{q}_{i}$-$\mathrm{LWE}_{q, \Psi} \text { to } \mathrm{DecLWE}_{q, \Psi}^{i}$ (Lemma 5.9). They say nothing about the properties of the guess, $g$, although they do go on to consider whether $g\equiv s$ mod $\mathfrak{q}_{i}$ or $g \not\equiv s$ mod $\mathfrak{q}_{i}$. My question is: what can we assume to be true about $g$? What can we say about its distribution? about other behaviour modulo $\mathfrak{q}_{i}$, or in the ring? Or can it have no more structure than merely being a ring element?


texts: HMAC_DRBG Generate Process: requesting N bytes at once different from requesting N bytes in total?

texts:
Am I correct in assuming that HMAC_DRBG would return different results if I, e.g. first request 4 bytes followed by a request of another 4 bytes instead of asking for 8 bytes at once?

It seems that in NIST SP800-90A chapter 10.1.2.5: Generating Pseudorandom Bits Using HMAC_DRBG first the K and V values are changed, then the requested number of bits is generated (changing just V), and then the K and V values are changed again. Besides that, leftover bits get chucked away as well.

Isn't it a strange property for a DRNG to return different value if DRNG(4) || DRNG(4) != DRNG(8) if the DRNG is not reseeded in between? Do other DRNG's have the same kind of property?


texts: How to calculate CPA attack complexity in bits manipulation

texts:
The following Forward Errors Correcting FEC is used in our daily devices. But I added a potential security measure.
In one of FEC systems the input is $K$ bits and the output code is $M$ bits where $M=3K$. The legitimate user at the other end uses FEC decoder to get the correct $K$ bits.
The proposed security is that if only $N$ out of $M$ bits are selected for transmission in the same order of $M$ in a way the receiver still can decode successfully. The number of $N$ bits and there positions in $M$ are generated by pseudorandom number generator with nonlinear structure driven by a key that changes every block of $K$.
The FEC decoder is able to decode only if $N$ and the positions are known so the unselected positions at the sender are filled by $M-N$ bit $0$ before decoding. The attacker does not know the key so $N$ so he won't know $M$ and $K$. In this system $K>500$ bits and the length of PRNG $n=100$.
How we calculate the number of CPA attack possibilities here?


texts: How to decrypt Pohlig-Hellman cipher if e and (n-1) aren't relatively prime

texts:
I couldn't find any articles that addressed to how to decrypt c after it was encrypted using the Pohlig-Hellman cipher if $e$ and $n-1$ aren't relatively.
Can someone please tell me how to do it?
I couldn't find an questions about this on StackExchange.


texts: Are modes of operation algorithms practical?

texts: I took a cryptography class back in college, and now that I am working my 1st career one of the things currently on my plate is coming up with an algorithm to encrypt data before it's placed on the server (In this case it's pretty sensitive info). I remember different modes of operation from that class like cipher block chaining and things of the like. I know that some of them are pretty hard to crack, but since they are so commonly known is it even practical to consider using something like that as an encryption method considering the algorithms for encryption and decryption are commonly known (from a security perspective)?


texts: Repeated modular square roots to recover original base

texts: I'm given a large prime $p$ and $c \equiv m^e \pmod p$, and $e = 2^{64}$. Typical RSA rules don't apply here, since $\phi(p) = p - 1$ is even, and $e$ is a power of two, so they share a common factor, specifically $\gcd(\phi(p), e) = 2^{30}$. I was thinking of applying repeated modular square-rooting, and since $p \equiv 1 \pmod 8$, I can apply the Tonelli-Shanks algorithm to get two square roots of $c \pmod p$. However, repeating this until I reach $m$ would give me $2^{64}$ possible plaintexts to sift through. I know that the plaintext $m$ is 42 bytes long and I also know the first 6 bytes, and the last byte. How can I eliminate square roots before I go all the way down the "tree"?


texts: Given a secure PRF $f(k, x)$, is $f(x, k)$ also a secure PRF?

texts:
Let $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ be a secure PRF.
Define $F(k, x) = f(x, k)$.
Is $F(k, x)$ also a secure PRF?


texts: How to correctly (good practice) generate gpg keys in batch mode (unattended) WITH a passphrase

texts:
I'm writing a web interface in PHP to generate keys. I'm familiar with gpg's command line options, particularly --batch. I'm also familiar with PHP's GnuPG API.
I can't find a way to safely pass the user's password from the web interface to the gpg command line because gpg uses a pinentry program? PHP's GnuPG functions don't include an API to generate keys.
What other way is there to generate keys, unattended, other than creating a batch file with the passphrase in that file like so:
Key-Type: default
Subkey-Type: default
Name-Real: Bob
Name-Email: bob@gmail.com
Expire-Date: 2021-12-25
Passphrase: mysecretpassphrase
%commit

Note: putting the passphrase on the command line with --passphrase is not wise.
Thanks!


texts: Signature verification with only hash (without full data)

texts:
I am looking for a way to sign a file, such that someone else can verify that I had this file, even if they only know a hash. I want to prove that I have the full file to someone who only has the hash.

More specifically: Alice has a large file (data). She creates:

a hash of data = X
a hash of (data + some message (e.g. her ID)) = Y

Both are public. Now Bob only has X (the hash of data), Y, and her ID (but not the data itself). He has to be able to confirm that Y was created using the data, but he should not be able to create Y without access to the data.

I guess what I want can be approximated by deriving a key pair from data and signing the ID with it (X would be the public key, and Y would be the signed ID). The problem with this idea is that someone else could precompute the private key, and pass only that to Alice. She then could compute Y without ever seeing the data. I'd like to require that Alice has to have the full data to create Y.

In particular Alice doesn't need to prove that she still has the data. It suffices to show that she had it at one point in time. The resulting protocol should be non-interactive, i.e. Alice publishes X, Y and ID and then someone can verify that they fit. I also don't need to protect information from Bob. He knows the hash X, and in principle can use it to lookup the data somewhere. It's just really inconvenient for him, so the protocol should allow verification of Y with only X and ID. If he could use the full data and ID to verify Y, then this would be a plain old digital signature.

This scheme I'm looking for seems like something that should already exist and have a name, and I don't want to MacGuyver my own crypto if not neccessary.


texts: Proving statistically hiding for a simple commitment scheme in the ROM

texts:
It is well known that one can construct a simple commitment scheme in the random oracle model (ROM) by setting
$\mathsf{Commit}(m;r) = H(r||m)$, where $m \in \{0,1\}^k$, $r \in \{0,1\}^{2k}$ and $H: \{0,1\}^* \to \{0,1\}^k$ is modelled as a Random Oracle.
My question is: How can I formally prove that this scheme is statistically hiding?
Intuitively, the RO is "compressing" and therefore there will be enough random strings $r, r'$ such that a challange commitment $c$ in the hiding experiment can have preimages of the form $r||m_0$ or $r'||m_1$ with similar high probability, so even an unbounded adversary has negligible advantage in the experiment. But that is merely an intuition and not a formal proof. I would be really thankful for some advice on how to prove the statement.
(Additionally I'm wondering if random strings $r$ of length $2k$ are enough to achieve statistically hiding. Maybe one can see in the proof that we need a longer random string.)


texts: How Should Multiple Checksums Be Performed On the Same Data?

texts:
I am using CRC32 to verify the integrity of received UDP packets. Along with the generator polynomial, the sender will also specify how many checksums to perform on the sent data, as well as what iteration to start at in its body. How should this be done?
For example, say I am sent this data
100100001

And this key
1101

Then I would normally do a CRC check like this
     _______________
1101 ) 100100001
     + 1101,,,,,
       ----,,,,,
       01000,,,,
      + 1101,,,,
        ----,,,,
        01010,,,
       + 1101,,,
         ----,,,
         01110,,
        + 1101,,
          ----,,
          001101
          + 1101
            ----
               0

At this point, I can verify that my data has not been changed or altered since the remainder is zero. However, if the sender specifies that multiple checksums should be done from a certain starting point, where exactly do I go from here?


texts: How is a Yubikey static password derived from the AES key?

texts:
When I configure a Yubikey slot as static, it's not documented or obvious how the static password yielded by a press relates to the AES key I set.  For example:

me@mine:~$ ykpersonalize -1 -ostatic-ticket -ofixed=cccccccccccc -a00000000000000000000000000000000
Firmware version 2.3.3 Touch level 1795 Program sequence 9

Configuration data to be written to key configuration 1:

fixed: m:cccccccccccc
uid: 000000000000
key: h:00000000000000000000000000000000
acc_code: h:000000000000
ticket_flags: APPEND_CR
config_flags: STATIC_TICKET
extended_flags:

Commit? (y/n) [n]: y

me@mine:~$ cat >/dev/null  # and do a short press...
ccccccccccccncejelrjvjvvciclerknrlihnteljrcb

Where does the key-based part (ncejelrjvjvvciclerknrlihnteljrcb) come from?


texts: How to detect if n long messages have encrypted with the same one-time pad?

texts: I have a slight idea on what the attack would be. But my question is: how would one detect if n long messages (n>5) have been encrypted with the same one time pad, K?


texts: Is it possible to create an open-source SecurID?

texts:
As far as I understand it, the hardware key-fob two-factor systems such as RSA SecurID depend on secret algorithms, and employ tamper-resistant hardware to prevent reverse engineering.

Is there some mathematical fact that prevents a system like SecurID from operating with open-source software (including the server and token algorithms, hardware token provisioning server) and hardware?

I would assume that, in the past, power requirements prevented the use of public-key algorithms in these little tokens. If it were designed today, would it be feasible to use that sort of approach in long-lived portable hardware tokens?


texts: What may be causing conflicts in Whirlpool implementation versions?

texts:
I see by layman articles (e.g. at Wikipedia) that the Whirlpool hash function has seemingly three current versions. That is to say, they are referenced as Whirlpool-0 (original reference code), Whirlpool-T, an optimised for hardware version which was changed to whirlpool (let’s call it “current”) due to a somewhat weakening in a diffusion matrix (according to article).

Now, I see some python implementations do indeed use that “current” version. However, I have been using librhash on Linux (i.e. rhash -W \$file) and I’m verifying things with OpenSSL (openssl dgst -whirlpool \$file).

OpenSSL and rHash are consistent with each other, but different from the current version. I also noticed that OpenSSL and rHash do not seem to correlate to either of the previous versions.

Why is this so? Has there been some undocumented update to the default Whirlpool s-boxes or something? Is there a version conflict, or has there been a Whirlpool update I may have missed?


texts:
Is there a way to take key material (for example 256 random bits for an AES key) and "expand" it over to a larger amount of data? Or can I go the opposite way and take a large amount of random data and Xor it down to 256 bits and use that (this looks like secret-sharing, but I do not know if anything changes because the "participants" would all be in the same place)?

I want to store a key, but I don't want it to be just 256 bits since it makes it hard to destroy it on certain types of media. The "key" should be a very large file such that if any portion of it on the media is damaged, the entire key is unable to be retrieved.

Just to be clear, I do not want to have "extra bits" of security. I just want to be able to have 256 bits (or whatever the algorithm is using) of security over a larger amount of storage to make key recovery on the physical storage media harder.


texts:
I am designing a protocol that will have security in mind as one of its key goals. Currently I have selected SSH with TLS as the underlying transport.

I selected SSH because it had a variety of extensible authentication methods built-in already, which would not only make it easier to add my own in the future but (in some cases) make it unnecessary to add any at all, depending on how the user wants to authenticate themselves. It also has file transfers built-in, which is a nice bonus for me too.

With that in mind, should I continue using SSH over TLS, or is that overkill? Or should I switch to using normal non-SSH-based sockets?

Side note: this protocol will not be used to access remote systems via a command terminal.


texts: Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-QuantumWorld

texts:
In this paper (Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-Quantum World), author describe password authenticated key exchange scheme on page 9 and 10 (see Fig. 1 on page number 10).

I have following doubts in my mind

  How initially new user starts communication with the server. Whether there is any registration process for new user?
  How server gets the client password, as in the protocol client do not send any password. On the contrary, server verifies it as $\gamma$' = -H1(pwc) where pwc is client password. I think Server may ask for password from client during registration phase and then store it in its database but i am not sure.
  In Fig. 1 on page number 10, client send $<C,m>$ to server. Is 'C' is client's id or sid or something else. As author do not give any description of it.
  Similarly, S is in session key formation skc= H4(C,S,m,$\mu$,$\sigma$,$\gamma$') in Fig.1. Is S is server id or sid or something else?

Please Guide.


texts: My understanding of ECDSA signature length is that it depends on the key size. So for instance, if a "prime256v1" is used, the signature length will be 64 because (n/8)*2 and for "secp384r1" it will be 96. However, I don't understand why is it for "secp521r1" the signature length is 132 instead of 130?


texts: Can I use a block cipher in CTR mode to generate keys from a master key?

texts:
Suppose I have an AEAD mode based on a block cipher that requires two or more keys.

In some cases, there is a complex proof that one key suffices.  But finding such a proof is hard.

An alternative is to use the block cipher in CTR mode to generate a pseudorandom stream from a master key, which is then split as needed into the needed keys.  It seems to me that this is always secure (assuming that the block cipher is itself secure, which you almost always are assuming anyway).  It is also simple to implement in both hardware and software, allows you to use a longer nonce, and helps with birthday attacks if the extra nonce (used for CTR mode to generate the subkeys) is itself a "nfewtimes" (I don't think the distinguisher against CTR mode is of any use to an attacker until most of the full codebook is exhausted).

Is this recommended?  Assuming you can't just use EAX or CCM, that is.