texts: How do P2P clients like uTorrent maintain authenticity of files?

texts:
I am very new to concepts of cryptography so bear with me and feel free to fill in any information that may seem obvious but something you think someone may not know.

At first I was under impression that people use checksums to determine if files are legit or not. Which didn't make sense for obvious reasons… for example it's not hard to get the same sum for different numbers. So all a hacker has to do is make a file with smaller sum and then fill in the rest with garbage that way file would have equivalent checksum, but completely different content. Then later on, I found out that a checksum isn't used at all for this purpose.

So, what is used instead? I’ve been reading that some asymmetric functions are used and that files are encrypted using the destination's public key.

But I am unable to wrap my head around it and say* “ok, this will work in P2P”*.

Let’s say there are files $A$, $B$, $C$ among 10 seeders and I am the receiver. And chunks of them are being sent. How does uTorrent make sure that the chunk received is the chunk it should be getting. Sometimes there is only 1 seeder. So the option of checking what most people have is out of the question…

Thinking about it ,I am not sure how uTorrent or P2P clients really work after all.

For example:

Does each torrent file has some unique ID? If, how is it generated?
Am I correct to believe that all torrents connect to a server to get the list of all other people?


texts: Index of coincidence for completely random text over k alphabets

texts:
I'm confused about /Friedman's method 2 (using a table with column of k size of key, and n/k rows, n is the total size for cipher text)

\begin{equation}
m = \Bigl(\varphi(l)-\varphi(o)\Bigr)/\Bigl(\varphi(T)-\varphi(o)\Bigr)
\end{equation}

P.S.
$\varphi(l)$ - stands for index of coincidence for language
$\varphi(T)$ - stands for index of coincidence for language
$\varphi(o)$ - stands for index of coincidence for completely random text

Just don't know what is the value for $\varphi(o)$ how we calculate it?
and m - stands for how many slice we divide the cipher text to analysis or the key size?


texts: Are the definitions of IND-CCA secure and of IND-CCA secure under standard model identical?

texts: Suppose there is a public key cryptosystem based on the discrete logarithm problem and let this cryptosystem be IND-CCA secure under standard model. Does this statement mean that the given cryptosystem is IND-CCA secure if Diffie-hellman assumption holds (that is the problem on which the given cryptosystem is based) or there may be any other assumptions (problems)?


texts: Decrypt the same ciphertext to multiple messages of my choice if I can use any key I want to decrypt

texts: In a modern secure encryption scheme, is it possible(both theoretically and practically) to encrypt a message using a key to get the following ciphertext c = Enc(M1,k1) and later find another key so that a different message of my choice gets encrypted to the same ciphertext c = Enc(M2,k2)?


texts:
If we have a hash function $h(x)$ and then a hash function $H(X) = h(h(X_0) || h(X_1))$ where $X_0$ is the first half of $X$, $X_1$ is the second half of $X$ and $||$ is concatenation. Then assuming we can easily find a collision for $H$, then it would be easy to find a collision for $h$ as well - Therefore finding a collision for $H$ is as hard as finding one for $h$.

Why is this? I can to some extent understand why that might be the case, but I can't logically connect the dots. Can anyone help me with some logic or math behind it or link to some resources where it is explained. I have tried google, but without the precise correct terminology I'm having a hard time finding the right pages.

Thanks


texts:
In terms of cryptography, how secure is Apple Secure Notes? Can one store sensitive information there? The relevant section of the Apple white paper is quoted below:

The Notes app includes a Secure Notes feature that allows users to protect the contents of specific notes. Secure notes are encrypted using a user-provided passphrase that is required to view the notes on iOS, macOS, and the iCloud website.
When a user secures a note, a 16-byte key is derived from the user’s passphrase using PBKDF2 and SHA256. The note’s contents are encrypted using AES-GCM. New records are created in Core Data and CloudKit to store the encrypted note, tag, and initialization vector, and the original note records are deleted; the encrypted data isn’t written in place. Attachments are also encrypted in the same way.
When a user successfully enters the passphrase, whether to view or create a secure note, Notes opens a secure session. While open, the user isn’t required to enter the passphrase, or use Touch ID, to view or secure other notes. However, if some notes   have a different passphrase, the secure session applies only to notes protected with   the current passphrase. The secure session is closed when the user taps the Lock Now button in Notes, when Notes is switched to the background for more than 3 minutes, or when the device locks.


texts: Why MACs are so important despite digital signatures doing everything a MAC can do and more

texts:
When an entity A wants to send a message to entity B, he can attach a MAC to the message. Entity B on receiving the message can use the pre-shared key to compute the same MAC and confirm if the message is untampered with.

This approach protects A and B from an external attacker who might want to mess with the message. However, it does not protect A from B or B from A. For example, A can craft a message and claim that it came from B since B is the only entity that shares this particular key with A.

Digital signatures eliminate this problem, since the MAC is replaced with a hash which is encrypted with the senders private key. Usage of the private key means that A and B cannot deny or forge messages between each other.

Which brings me to my question. Why do MACs continue to be so relevant when they are susceptible to the kind of attack described above? Under what circumstances would one prefer a MAC to a digital signature?

Note that I have been made aware that there is a question on here which seeks for a comparison between MACs and digital signatures. That question is different from mine since I am looking for concrete cases where MAC would be used instead of digital signatures. Can someone quote a protocol, application, etc, where the disadvantages of the MAC relative to digital signatures can be ignored?


texts: Is there (this) a case in which salting is dispensable?

texts:
tl;dr this is not a duplicate of "what is a salt/why use salt?" question. Instead it is specificly asking when salt may not be necessary for hashing securly? (i.e. when the data being hashed is already as high-entropic as that chances for duplicates is very very low)

Reasoning underlying the question
To my currently best understanding, it is that

salting is prevention against the usage of rainbow tables. (and only that)
rainbow tables are stored up precomputed original-data,hash-value pairs for a set of more or less frequently occuring original-data (i.e. the 100,1000...10^x most often used passwords)
rainbow tables are increasingly useless, the more and more random/entropic the original-data is. (The sum of all passwords used today may be very well smaller than 2^64 and hence less entropic than a truly random 64bit value)

My question is, that given that my assumption 3. above holds, then I would expect that salting (given 1. holds) becomes an decreasingly necessary endeavour.

Can this be confirmed or contradicted, please?

This is not only an academic question, but I have stumpled upon it in real life™ and maybe this serves as a way to bring this question also to a practical and henceforth more understandable / answerable level.

The case is that looking back at some work I have started prior to become crypt.stackexchange.com user I see with shock that I have stored data in a database in a plaintext fashion, that is used for authetification. In the very case it is a nonce created for an email verification (which is sadly anyway an unsafe channel, yet not in my power to prevent and not the issue here).
The nonce is unique and created from /dev/urandom. With hashing I would prevent that somebody having access to the database can access the nonce. If it was a password I would use a salting when storing it (because as mentioned I prevent rainbow-tables).
I think a rainbow-table for my 128bit value seems to defy its purpose as and I really wonder if I need to salt the unique nonces?


texts: What is blindness and forgeability in Chaum's blind signature scheme?

texts:
I am going through the voting protocols. I know how blind signature works (Blind Signature), but why is blind signature - unconditionally ”blind”, conditionally ”unforgeable" (as highlighted in the following paragraph). How do you define blindness and unforgeability? Please explain. If possible give an illustration.

There is a possibility of guaranteeing the anonymity of voting unconditionally by means of conventional, i.e. classical cryptography, based on mathematical encryption. The corresponding voting protocol is based on the principle of ”sender untraceability”, meaning such a communication scheme, where the recipient of several messages from several senders cannot determine which message came from which sender. Such a communication can be realized with unconditional security in the sense that the recipient is unable to establish any relation between the messages and the senders, even being in possession of infinite computational power. However, the very property of untraceability creates, in the case of voting, an additional problem of determining which ballots come from legal voters, since illegal participants can send ballots in an untraceable way. This problem is solved by a special ”ballot issuing” protocol (based on the technique of ”blind signature”) providing each legal voter with an ”unforgeable” and ”blind” digital ballot, which is used for sending a vote. The term ”unforgeable” means that the ballot cannot be cloned, while the term ”blind” means that the ballots are in no way related to the identities of legal voters. The ballots in the ballot issuing protocol are unconditionally ”blind” but only conditionally ”unforgeable”, that is a person in possession of rich enough computational power is able to vote instead of legal voters. Thus, the property of ”non-exaggeration” is realized by the overall voting protocol in a conditional way only.


texts: Is there any practical use of reduced rounds of AES

texts: There are lots of attacks which are on reduced block ciphers. There are practical attack on five rounds of AES-128five rounds aes broken in six minutes. I was just wondering if there is any practical application of reduced rounds of AES where less than 10 rounds are used.


texts:
I'm trying to understand this LWE public key system

say I use matrix A = [[44, 73, 20, 54],[92, 19, 78, 22],[31, 34, 94, 29],[82, 32, 70, 68]]

q = 97

bit = 1

and secret key s: [56, 90, 0, 46]

and secret error vector e:[1, 0, -1, 0]

then B = As+e mod q is [73 17 18 27]

Bob's secret is [1, 0, 1, 1]

Bobby computes u = A*x mod q and get [21, 95,57, 26]

and v = Bx + bit(q/2) mod q and get 69

Alice decrypts:

v-s*u = 69 - 58 = 11

11 is quiet far from q/2 = 48

what am i doing wrong?


texts:
How many plaintext-ciphertext pairs would be needed to guess with probability, say $p=0.5$, the key $k$ of AES under ECB mode?

Most of the articles that I found tried attacks on single plaintext-ciphertext pair. How would the chances on attack on key increase with increase in number of plaintext-ciphertext pairs.

Link to document or discussion thread about various attacks would be highly appreciated.


texts: Sharing RSA private key between SSH and SSL services. How bad is it?

texts:
An appliance uses a curious way of obtaining ssh-rsa host keys: There is a single configuration option "management certificate" that sets RSA private keys both for HTTPS and SSH management.

Concretely, the configured certificate+key is used as-is for HTTPS. For SSH the device extracts and reuses the raw RSA key from the certificate (modulus N, public exponent e, private exponent d)

My question is: Is this "only" bad practice or a potential vulnerability?

Follow-up question HERE: What arguments can be used when communicating with the vendor?


texts: Is the any QR code with built-in hash of the information?

texts:
For example, the text is something like

"Hello world!"

And after that text should be new line with hash (sha256):

9e77bdb7b7b67bee57fe10946ac0275e38585c688ace439d96d82ebf71c26496

So, now it is not possible to modify QR code (recoloring some squares) without loosing it.

Is something like this implemented for QR coding outside, where it is possible to modify the code?


texts: Can Reed Solomon parity blocks be used as an all-or-nothing transform?

texts:
Consider the following scheme:

Perform an (N,N) Reed-Solomon encoding (i.e. N data blocks, N parity blocks)
Drop the N data blocks and keep only the N parity blocks.

Are these N parity blocks an all-or-nothing transform? (meaning missing even one parity block does not permit decoding the original data blocks)


texts: What if the CSR is intercepted in transit while sending it to CA?

texts:
I was studying PKI the other day and I had a serious thinking about the following question.
What is CSR?  - It is a block of encoded text that is given to the CA when applying for an SSL certificate which validates the identity of the requesting party. The process to construct a CSR is,

A Certificate Request Info value(plain-text) containing Distinguished name has to be filled. i.e. Common Name, Organization, OU, City, State, Email Address and Public Key.
The above Certificate Request Info value is signed with the subject entity's private key. i.e. Digitally signed.
The Certificate Request Info value, a signature algorithm identifier, and the entity's digital signature are collected together into a CSR.

So, basically the CSR contains Digitally signed plain-text info about the requesting party, the plain text-info and the Signature Algorithm.
My question is What if the Man-in-the-Middle alters the Email Address in the CSR but actually kept the public key intact?
This way when the CSR reaches the CA, the CA will fetch the public key from the plain-text info and decrypts the signed info thereby assuming that no tampering was done. So, Is there a way to prevent this interception or my understanding is incorrect?


texts: Problems about parameters configures of Herrmann and May's method to solve linear modular equation

texts:
I'm reading Herrmann and May's paper; they introduced a method to solve multivariate linear equation modulo unknown divisors.

It's shown in Table 1 that, for an 512-bit RSA modulus N with divisor p of
size $p \geq N^{1/2}$, experiment with two blocks, each for an 45 bits unknown, yields $m = 15$.

But according to what they mentioned previously, define $$X_1 X_2 := N^{3\beta - 2 + 2(1 - \beta)^{3/2} - \epsilon}$$

and fix

$$m = \lceil{\frac{3\beta(1 + \sqrt{1 - \beta})}{\epsilon}}\rceil$$

I figured out that $\epsilon = 0.030955, \space m = 83$, which are far from their results.

What's wrong with my parameters, or did I miss something?


texts: Rapid partial block decryption of compute intensive full encryption

texts:
Given a block of data D: Is there a encryption/decryption scheme that would allow me to perform a resource-intensive (compute/time/memory) encryption of the full data set with a key k, but allow for a rapid decryption of arbitrary constant-length parts (say 64 bytes) of this data set?

Encryption key k is known to the decrypting instance.

Example: Data set is 65536 bytes and will be encrypted by key k. This encryption can be O(n), O(n²)

Now consider the encrypted data to be an array of 1024 x 64 byte data chunks: Can I decrypt an arbitrary chunk D[i] (for i [0,1023]) in O(1) ?


texts: How do byte-sliced AES implementations work?

texts:
While I understand the principle of bit-slicing, several papers  mention byte-sliced AES implementations (see e.g. Homomorphic Evaluation of the AES Circuit and Fast Implementations of AES on Various Platforms).
However, I don't clearly understand how byte-slicing works. Especially, one can read in the above mentioned papers that:

16 blocks are processed in parallel
The permutations in ShiftRows/MixColumns are now "for free"

Could someone explain how byte-slicing works in the case of AES, and how it allows to process 16 blocks in parallel without computing the ShiftRows?


texts: What are the vulnerabilities of XOR in the following scenario?

texts:
What are the security vulnerabilities of the XOR operator in the following scenario:

The Key, The Cyphertext and the Plaintext are the same size in bits.
The Key is only used once and it's secret
The Plaintext is only used once and it's secret
Hence the Cyphertext is only used once, but it's public
Only the Cyphertext, and hence the size of the key is known to the adversary

However:

The Key was generated by a pseudorandom number generator
The Plaintext (which is a private key to something else) was also generated by a pseudorandom number generator

Therefore neither the key nor the plaintext is fully random, vulnerable to frequency attacks.

So I don't care about practical issues, like the difficulty of key sharing. I only care about security issues.

We can identify that this setup can be vulnerable to frequency analysis and such described here:

https://stackoverflow.com/a/1135204

But are there other vulnerabilities besides the pseudo-random nature of the key and the plaintext?
If both the key and the plaintext were truly random, would this provide perfect secrecy?


texts: Is compressing data prior to encryption necessary to reduce plaintext redundancy?

texts:
As explained in William Stallings' Book, in PGP encryption is done after compression, since it reduces redundancy.

I couldn't relate encryption strength with redundancy. Could anyone explain more on that?


texts: Can a compressed checksum be considered unique

texts:
I'm kind of guessing that the answer may be no. Since the compression is trying to reduce the output size using various optimization methods, this may cancel the properties of a hash algorithm.

But take the following Python code:

>>> import zlib
>>> import hashlib
>>> zlib.compress(hashlib.sha256('data'.encode('utf-8')).digest())

Can the output from the zlib compression be considered unique?

Note that since the hash value is quite random, it cannot be compressed efficiently:

>>> len(zlib.compress(hashlib.sha256('data'.encode('utf-8')).digest()))
41
>>> len(hashlib.sha256('data'.encode('utf-8')).digest())
32


texts: reusing blowfish algorithm to implement bcrypt

texts:
I'm trying to implement bcrypt and have a really fast Blowfish implementation available to me. It seems to me that the existant Blowfish implementation is not going to be able to be leveraged to implement bcrypt since the bcrypt key expansion kinda interleaves the salt and key together whereas Blowfish's key expansion doesn't make use of a salt or anything like a salt.

Is that a correct assumption or is there, in fact, a way to leverage an existant Blowfish implementation that I'm just not seeing?


texts:
Say you run in to a messed up AES (128) implementation which has the s-box configured as [0x0, 0x1, ..., 0xFE, 0xFF] and where you can query a few plaintexts to get the corresponding ciphertexts.
How many queries would one need to be able to deduce the key, and how would one go about it?
This would be a chosen plaintext attack, but I fail to see how it would be done.
Thanks a lot.


texts:
What is the purpose of SDES algorithm?  (Session Description Protocol Security Descriptions)

What are the problems in the way it exchanges keys?

I have tried to search about these quastions but i couldn't find any understandable reasons.
Please help me.


texts: How safe is XOR with multiple independent but non random keys?

texts:
I will approach the question from practical side. All the examples are not  real, but for illustration purpose only.

I have a message, the secret Bitcoin key, which I want to store safely.

MESSAGE = KwjwmREseNZmZ8yeNKrurN6qPuh9FhrLAefYa2nTLafLkGmWW9ta

To do this I come up with 4 keys which look independent,  somewhat private, and can be recovered.

Key 1 is a set of last words from page 100 and up in my favorite book to match the message length:

KEY1 = help knows the at sortes state the citizens color science costs unfairness

Key 2  is the Merkle Root from Bitcoin blockchain block number 121047, which could be my 2 kids' birthdays 121 and 047 (for the day number within year easily available at blockchain.info)

KEY2= 1b28458e4191e60f4553357cb7b54a9cc15ea0a27e8f5df27dab6d3aab3d3be4

Key 3 is the name of the file of my main wedding photograph, stored in my albums, mail, and shared with friends.

KEY3= IMG_20170511_144510.jpg

Key4 is another Bitcoin address generated solely for the purpose of being a key, two copies will be stored in home safe and safety deposit box in the bank

KEY4= L1jkNAKpG1hu7omtYW6fFFDGw1AaYrdkiUr4NpBANziKVHdZgx8v

The keys are not re-used anywhere. KEY3 is replicated to match the length of the message. The message and all keys are XORed (byte by byte) to get the secure code.

The question is:  How safe is the resulting code?  Can I store it online? Can security hold if 1 or 2 keys (but no more)  are compromised?

I understand that there might be no correct answer, but would appreciate any thoughts  if I miss some vulnerabilities.  Should I have more keys? What kind of keys would help? Can I mix in more plain text keys?

If you ask why not to use a password with good encryption, it is trickier for me to verify the program doing the encryption, while doing XOR is trivial in HTML with few lines of JavaScript on any old offline smart phone (to be destroyed afterwards), and will be trivial in the future.

Thanks.

PS. I can try to figure out how to post the HTML doing the job if anyone is interested.


texts: How does a Padding Oracle Attack work in practice?

texts:
I have understood how the padding oracle attack works in theory. Now, I am trying to visualize it in a real scenario.

Can someone please give a real scenario in which an attacker can insert himself in the channel and send cipher texts and be able to receive the error messages indicating success or failure of encryption? I am struggling to establish how this attack would work.


texts: Cryptography scheme to prove you really are the author for something

texts:
Say I'm a researcher like Satoshi Nakamoto that wants to stay anonymous. I want to publish documents and sign them somehow. A few years, I want to reveal my identity and prove it was me who was Satoshi all along.

Is there a cryptography scheme that can be used to achieve this?


texts: Hardware random number generator for lottery?

texts:
To be able to generate random numbers for lottery games, we have the following requirement:

  The random number generator, which uses the deterministic algorithm to determine the game result, has to work with a length of at least $$2^{64}$$ period to ensure that the random process is generated so that in the case of a particular gambling there is no detectable repetition of the results, and must produce a sequence of game results based on initial values that are random or unpredictable

What does it mean in terms of certifications and hardware random number generators?

Am I able to fullfill the requirement with hardware device which is compliant with P2 Class of BSI AIS-31 (for example CryptoMate64 USB cryptographic dongle or other HW certified cryptographic device according FIPS 140-2 Level 3)?


texts: How to store keys for a cascading encryption?

texts:
What is the best way to implement a cascade encryption?

I'm trying to figure out how to cipher a string (or message) using Serpent-Twofish-AES and then store the keys.

I'll provide an explanation, then maybe someone is going to be able to explain how to resolve the issue I'm facing. I've read the TrueCrypt documentation before posting here.

Let say Anna want to send an email to Bob. Anna type a password and give it to Bob face to face.

Message being sent over internet: Hi Bob, this is Anna

I split the message into chunk.

#1: "Hi Bob,"
#2: " this i"
#3: "s Anna"

After that, each chunk is encrypted with AES then Twofish and then with Serpent.

Key #1 encrypt Chunk #1 with AES
Key #2 encrypt Chunk #1 with Twofish
Key #3 encrypt Chunk #1 with Serpent
Key #1 encrypt Chunk #2 with AES
Key #2 encrypt Chunk #2 with Twofish
Key #3 encrypt Chunk #2 with Serpent

And so on...

Then all encrypted chunk is stored somewhere...

The keys are generated based on the password Anna provided.

Where do I store the keys?

I didn't find any useful information about implementing a cascade encryption and I think this question might be good for the internet's knowledge.


texts: Why still we are using classical key exchange rather than quantum idea

texts:
Why still we are using Diffie-Hellman idea  rather than BB84 or B92 like
quantum protocols for key exchange?


texts: Proving item association without revealing one of the associated items

texts:
I'm a total noob when it comes to cryptography but I believe this falls under the "zero knowledge" category.

I have two associated pieces of information:

tag — known by both parties. Unique per scenario.
identity — known by only one party. Potentially associated to multiple tags. Comes from a pool known by both parties.

I need a way to prevent the party with the association from changing the value of the identity. There are around 100 concurrent associations per scenario. The pool of potential identities can be relatively small, even smaller than the number of tags, but can be larger too.

The most primitive option would be to hash the tag and identity together but with a possibly small pool of potential identities I fear it would be trivial to brute force the hash...

During the scenario more and more of these associations will become public. At least at that point I should be able to confirm that the other party did not modify the association. I don't really have to confirm this before then, because unrevealed associations are not relevant. I just need to prevent the knowing party from picking and choosing at the time of revealing. And I need to prevent the other party from deducing the identity before the reveal.

Is such a thing even possible? How could it be done? How difficult would it be to implement?


texts: Bleichenbacher 1998 "Million message attack" on RSA

texts:
I have been reading Bleichenbacher's 1998 paper on a forged message attack on RSA. The paper assumes access to an Oracle that takes a ciphertext $c$ and will check the decrypted text for valid PKCS #1 padding and returns the validity of the padding. This side-channel can be used for an attack since we can send a forged ciphertext by selecting random integers $s$ and compute:

$c' = cs^{e}\, \mbox{mod}\, n$

If $c'$ is PKCS conforming we know that the two most significant bytes of $ ms = c'^{d} \mbox{mod}\,n$ were equal to 0x00 0x02.
If we define

$B=2^{8(k-2)}$

where $k$ is the length of $n$ in bytes, then we know

$2B\leq ms\,\mbox{mod}\,n<3B $

Now we have a range $M_{0}$ in which we know $ms$ to lie:

$M_{0} = {[2B, 3B-1]}$

The attack now proceeds by iteratively generating more valid forged ciphertexts for integers $s_{i}$ and with the gained knowledge reduce the range of $M_{i}$

I am having trouble understanding Step 3 in the paper which deals with narrowing the set of solutions:

$M_{i} \leftarrow \cup_{a, b, r} \lbrace [\mbox{max}(a, [\frac{2B+rn}{s_{i}}]), \mbox{min}(b, [\frac{3B-1+rn}{s_{i}}])]\rbrace$

for all $[a,b] \in M_{i-1}$ and $\frac{as_{i}-3B+1}{n}\leq r< \frac{bs_{i}-2B}{n}$

How would this be implemented in code? It looks to me that we would need to compute each range for every $r$ within the specified bounds e.g.:

for (r=r_min; r<r_max; ++r)
    max(a, x);
    min(b, y);

However this seems to be intractable to me and I think I am making an error in trying to convert the math to code. Anyone maybe see where I am going wrong?


texts: Lattice-based cryptography prone to side channel attack?

texts: Is lattice-based cryptography still prone to side channel attacks? What are some mitigation strategies, if any?


texts: Do low-entropy fingerprints actually make any sense?

texts:
I'm thinking of ZRTP and OTR in particular here. From my understanding, after a Diffie-Hellman session is initiated, the shared secret is then hashed into a 4-digit number, which the two parties can then check out-of-band (or in ZRTP in-band, assuming that people can recognize each others' voices).

How is this possibly secure? The only articles I've read about the protocols say something like "there's only a 1/10000 chance that it's a man in the middle if the numbers match", but can't the man-in-the-middle pick his own private keys (by brute force) such that the numbers match? That is, with a setup like

Alice <- ss_am -> Mallory <- ss_mb -> Bob

could Mallory not use a brute-force search to find private keys such that ss_am and ss_mb hash to the same 4 numbers?

Or am I fundamentally misunderstanding something about ZRTP and OTR?

A related question would be the SSH public-key randomart thing. It has not a lot of bits of entropy, so couldn't an impersonator simply brute-force a private key such that the public key has the same randomart as the real public key?

This question probably also applies to ideas like generating gravatars from public keys so that impersonators look different, or the common practice of referring to PGP keys by their first few bits.

How can low-entropy fingerprints be useful?


texts: What was the NSA's reasoning for making their bitwise combination functions in SHA-1 the way they did?

texts:
I know that these functions are there to actually make the program work. What I want to know is why they made the functions one way but not another.
For example, why did they pick

  F1(B, C, D) = (B & C) | (~B & D)

as their first function instead of another function like

  F1(B, C, D) = (B & D) | (C ^ (D & ~B))


texts:
i am creating some primitive demostration for ECDSA over small curve (p < 229). But my implementation have some weird issues. Verify process return false even if the signature is correct. Because I am testing it for some time, trying to find problem I discovered that verify work only if point order is prime.

So my question is, is there some condition for point order? And what about point with non prime order? Don't use?

I have been reading some papers about ECDSA, but I didn' t find anything about that.


texts:
I have a number that consists of 102 digits and I need to factor it. I ran it in alpertrom.com.ar, but it'll take up to 40 hours if I counted all right. Is there any way to make it by hand (stupid question), I mean to simplify computation for the program? Or maybe anyone can factor it out. The professor is probably just testing our processor's computability.
Here's the number: 166045890368446099470756111654736772731460671003059151938763854196360081247044441029824134260263654537


texts: Unit testing a library RNG and its seeding for practical security

texts:
Suppose I have a cryptography library that provides me with a black-box random number generator that is supposed to be suitable for long-lived key generation.  (Under the hood it may be assumed to use some combination of /dev/random or equivalent, and stretching with a CSPRNG.)

I would like to write a unit test that can detect implementation errors that would result in practical failures of security.  For instance, it should reliably detect the infamous CVE-2008-0166 (Debian OpenSSL weak key generation) if applied to a version of OpenSSL with that bug.  Note that statistical tests as discussed e.g. in this earlier question will not do the job by themselves, because of the CSPRNG in between me and the guts of the black box (the CSPRNG itself has already been checked by use of test vectors).

How might this be accomplished?


texts: Double DES meet in the middle attack: probability that wrong key pair remains

texts:
My Question is based on poncho's answer in this post.

If you're doing a meet-in-the-middle attack against 2DES with only on a plaintext-ciphertext pair $(P,C)$, I understand that the expected amount of remaining key candidates is $2^{48}$, assuming that DES encryption/decryption yields a random 64-bit block if done with a wrong key.

What makes me curious now is: if you have another plaintext-ciphertext pair $(P',C')$ to validate the candidates, what is the probability that a wrong key still remains?

So my approach is the following:
We just start a new attack, with the reduced key set.
Since there are only $2^{48}$ keys left, the possibility of a specific block is $\frac{2^{48}}{2^{64}}$ which is $2^{-16}$. Is this is already the possibility I'm looking for?
If yes, then this leads me to the conclusion that despite the probability of one specific block is very small, there are still $2^{48} * 2^{-16} = 2^{32}$ candidates in the set!


texts: random mask reversible after homomorphic encryption

texts:
I would like to know if this process is feasible under homomorphic encryption, ideally under paillier or any other additive scheme

Apply a mask X to obfuscate a message A ie. Am = A (op) X where (op) can be +, x, ...
Homomorphically encrypt Am => E(Am)
Remove X from E(Am) in order to obtain E(A) without any decryption (without knowing the private key)

A can be a matrix, vector, ...etc.


texts: Threshold Secret sharing - How to create a shared secret from pre existing secret parts?

texts: In usual $(t, n)$ secret sharing schemes, a secret $S$ is split into $n$ parts so that any $t$ out of $n$ parts reconstruct the original secret. So, suppose that there is a group of $n$ participants each one has a secret $x_i$ ($x_i$ may be its private key). My question is, is it possible to create a secret $S$ using the prexisting secrets $x_i$ ($i=1...n$) so that with any $t$ out of $n$ from these secrets ($x_i$) we can find the secret $S$?


texts: Why I can't permutate an email and get away with it?

texts:
I can understand why a simple substitution cipher can be broken easily using English letter frequencies, and even English digrams like th can be used. Also a complete random substitution will have a key length of $26!$ which can be done (around $2^{88}$, maybe NSA).
But what about emails? According to Google, emails have an average word count of 400 words. So I guess letter count will be at the very very least 800 letters. Brute forcing $800!$ (assuming a completely random permutation function) is not possible.
I also guess English letter frequencies can't be used as these frequencies apply to all English words and these letters can be used to construct different words. But still, it's not secure to use only permutations for encryption.
So why is that? How to get around brute-forcing $800!$ permutations?


texts: Could a symmetric encrypted communication with a SHA-512 hash still be manipulated?

texts:
I just got back from an exam review and there was a question I remembered that I apparently got wrong. I wonder if someone could help me with this, since it bothers me.
The question was something like that:
Between a client and server, a symmetric encryption algorithm is used for the communication. The encrypted data is then hashed with SHA-512 and added to the data stream.
Would a man-in-the-middle be able to meddle with the message in a way, the software would not be able to identify the manipulation? It's important that the attacker does not need to get access to the content of the message or manipulate it in a meaningful way. Just the general possibility.
In my answer, I said that, yes, it was possible, but got 0 points on my explanation. I would be interested in the correct answer to that question, out of sheer interest.


texts: Can a key exchange protocol exchange a one time pad instead of a key?

texts:
As I understand key exchange, two parties can agree on a fixed number of secret bits in the presence of a listening adversary.  That set of bits forms a cryptographic key which is then used to encrypt data using a standard cryptographic algorithm.  And that key is repetitively used over and over, perhaps for an AES session.

What if instead of a key for cryptographic algorithms, a one time key was exchanged for use with a one time pad construct? My system would then exchange another pad for the next message.  Could you realistically securely exchange 1280 bits /160 bytes for a Twitter length message?

Note.  A true random number generator is available.

EDIT.  From initial comments, it seems that the security of the OTP key would be contingent on the security of the key exchange mechanism, say Diffie-Hellman, RSA or similar.  So I guess a fundamental part of my cunning scheme would be the ability to use a key exchange mechanism that provided > (160*8) bits of security.  Wouldn't that then mean  the security proof of the OTP was still maintained?  This is a theoretical exercise, so performance is not a consideration (unless we're talking of geological timescales that make it de facto impossible). Could it be done for example as one message per 24 hrs using a modern desktop machine?  An SOE agent might only send one message per week in WW2.  Just some temporal context.


texts: What does non-collusion assumption mean in server-aided protocol based on secret sharing?

texts:
Suppose $m$ clients split their own input into $n$ shares using additive secret sharing scheme (mod something).
Then, each of the clients sends each share to each of $n$ external servers.
After receiving the shares from the clients, the servers run MPC protocols where no client will be involved in the protocol.
(Later, some or all clients receive the output share from the servers and reconstruct the result.)

General assumption is on non-collusion assumption, meaning that the protocol is safe (at least no client input is leaked) as long as $t (\leq m)$ servers do not collude.

I have a question regarding the assumption.

Does the "collusion" mean any possibility that $t$ shares in the servers are somehow assembled?

If so, do the followings have all the same meaning in the assumption?

server operators are all malicious and share their information about clients' shares (and assemble them)
some clients are malicious and get access to more than $t$ servers to see clients shares (and assemble them)
some malicious guys (who are neither any of the clients nor any of the server operators) hack the servers and assemble the shares on them.


texts: What kind of symmetric-key algorithm to use with Diffie-Hellman?

texts: Let's assume we use DH with a cyclic group modulo p. As I know safe length of p must be at least 1024 bits. That means that generated key could be very big. But what do next? What kind of symmetric-key algorithm to use? DES requires key length to be exactly 56 bits. AES - 128/192/256 bits. We have no guarantee that key generated by DH will be n bits. It could be longer or even shorter. Do we have to reduce or extend key to fit it in AES or (3)DES? Or is there an algorithm that works with any key length?


texts:
I am currently working on a desktop TOTP client.

From the TOTP spec at https://tools.ietf.org/html/rfc6238#section-4.1, the 6 digit  OTP is generated from counter (in this case time).

But what is "time"? The spec says that the time is in the format of a Unix time epoch (seconds that have elapsed since Jan 01 1970).

My question is,

What how do I compute this Unix time?

a) Do I get UTC time & convert it to Unix time epochs?
b) Do I get local time & convert it to Unix time epochs?

or

c) Converting both UTC & local time to Unix time gives the same value so it will not matter?


texts: Solve a problem, thought it was hash length extension, hours later, am I wrong?

texts:
Here is my situation. I'm working with an application for which uses hashing to authenticate data.

I have a string, which is hashed. It is, like in a hash length extension attack, H(key:known_value)

This hash is incremented by a nonce upon repeated attempts. On the first attempt there is no nonce, further attempts are H(key:known_value:nonce)

I believe I misunderstood a hash length extension attack (and was up for 9 hours last night learning that) in that by knowing the hash value, and the length of that entire hashed string, that I could add a nonce and get the same hash?

Not sure if I'm making sense, so let me demonstrate with example values:

hash("IamSecret:YouKnowMe") = 389fiu3vb93h39v (yes, not a real hash)
hash("IamSecret:YouKnowMe:1") = f5d725d78223hjd2d2 (also made up)

I thought that a hash length extension would allow me to take the first hash, "389fiu3vb93h39v" and knowledge of the length of the secret (9) and the known data (":YouKnowMe") and append my data (":1") and come up with "f5d725d78223hjd2d2"?

But after 9 hours of messing with it, it seems thats NOT possible? What a hash length extension attack would allow me to do is to take my known values above, and come up with a string (something like :YouKnowMe\x80\x00\x00.......\x00:1) and figure out what the hash would be **IF I DID **hash("IamSecret:YouKnowMe\x80\x00\x00.......\x00:1")?

Is my understanding correct?

And if so, is there ANY way to do what my original issue was? I know the hash algorithm used, I know the hashed value of secret:known, I know 'known', I know the length of secret. Can I ADD DATA to 'known' and get the same hash that the client app would get if it just hashed secret:known:added_data?

I'm running on 4 hours sleep, sorry if my question is confusing :)


texts: Better security than SHA1 for signature?

texts:
An application that I maintain uses Sparkle Update to update itself. I expect attacks from high level attackers (China, USA's NSA, etc.) and have some questions about how secure the cryptography Sparkle uses actually is. Specific examples of good practices would be much appreciated.

Creating public/private signing keys.

Sparkle uses the following to create public/private signing keys:

openssl dsaparam 2048 < /dev/urandom > dsaparam.pem
openssl gendsa dsaparam.pem -out dsa_priv.pem
openssl dsa -in dsa_priv.pem -pubout -out dsa_pub.pem

1.1 Is using "/dev/urandom" a good idea on OS X?

1.2 Are there any other problems here? (I will probably generate a 4096-bit or larger key instead of the 2048-bit one.)

Signing the application

Sparkle protects from forged updates by signing the updates. It uses the following to generate a signature:

openssl dgst    -sha1 -binary < in-file | openssl dgst -dss1 -sign private-key-file

Would changing it to

openssl dgst  -sha256 -binary < in-file | openssl dgst -dss1 -sign private-key-file

(and changing the signature verification to verify the signature on a SHA256 hash, of course)

be enough to avoid the weakness in SHA1?

Or is there also a problem with "openssl dgst -dss1"?

Thanks in advance.


texts: Digital signature that is only verifiable by one specific person

texts:
I would like to digitally sign a message in such a way that the signature can only be verified by one specific person. Simply encrypting the signature will not work, because that person could then decrypt and publish the signature and everyone else would be able to verify it.

Does anyone know of a scheme to accomplish this? Or any other advice?

In my situation, the person verifying the signature has an incentive not to publish their private keys.


texts: NTRU Euclidean algorithm the inverse of f modulo p

texts:
I am very new to the world of cryptography and have just began my research in the post quantum cryptography sector. I have been reading and trying to understand NTRU key generation and am struggling to understand how to practically do the inverse of f. I know that this is solved using the Euclidean algorithm, but I am unable to figure out what the steps would be. I was hoping someone would be able to show the steps to solve the example shown on the NTRUEncrypt wiki page shown below (fp or fq), or a smaller polynomial that gets the point across. I am more interested in the practical steps then the theory behind it, as I have found many resources for that.
Thank you!


texts: zero knowledge proof for complete new user authentication

texts:
Consider an environment, an user A who is completely new to the environment is entering. An user B who is member of the environment need to verify A as genuine not liar.

No information about user A is known to B.

Is it possible using the zero knowledge proof.


texts: Does AugPake not require key stretching?

texts:
I was reading the AugPAKE rfc and noticed that there is no mention of key stretching anywhere. The protocol does mention use of a hash function, and the hash function that is provided as an example is SHA2.

It appears the protocol does not utilize computationally expensive key stretching anywhere. I would like to ask how the protocol can remain secure with regards to low entropy passwords. What prevents an attacker from brute forcing the weakest link in the chain?

It seems like there must be some form of rate limiting in order to slow down the search through such a limited set of possibilities. The only mention of this I saw was the standard recommendation of only allowing X incorrect password attempts per unit time.

Could it improve security to use a key stretching algorithm such as pbkdf2/bcrypt/scrypt/argon2 on the password, or would that defeat the purpose/efficiency of the protocol?


texts: Would adding daily changing nulls in front of their messages have made the Engima harder to crack?

texts:
The British decrypted the German enigma because they knew that they would repeat the message key twice at the start of every message.

Of course, technology to encrypt enigma without the repetition using cribs was developed later but only after it was cracked before.

The encryption key for the Enigma messages changed daily but what if the Germans also specified an amount of nulls before the message begins.
Then they wouldn't just have changed plugboard settings and rotor settings every day but would have also put X amount of gibberish in front of every message.

Would this have made the Engima significantly harder to crack?


texts: Can private key be specified on key pair creation?

texts:
Without regards to any specific implementation of asymmetric cryptography, I am wondering if it is feasible to come up with a value of private key I want to use, and calculate the corresponding public key from it.

The use case would be the creation of multiple private/public key pairs where the private keys are merely the concatenation of some masterSecret and the pair ID (the latter is publicly known). This way, whoever knows the masterSecret also knows all the pairs' private keys. This, in essence, makes the owner able to have multiple public keys linked to just one private key, which is ordinarily not possible.

Which asymmetric cryptography implementation/algorithm is reasonably practicable for this purpose, given that typical use for the calculated pairs would be SSH-like authentication?


texts: How can one validate with a public key a JWT signature generated with a private key?

texts:
As I understand it, a JSON Web Token (JWT) consists of 3 parts:

the header, specifying the hashing algorithm to use for the signature;
the payload itself; and
the signature, which is a hash of the header and the payload using the specified hashing algorithm and a given secret.

The point of the signature is for the receiver to verify the integrity of the received JWT, that it has not been tampered with. This is done, presumably, by the receiver of the JWT reproducing the steps made by the JWT producer to create the signature, by hashing the header and the payload with the specified hashing algorithm and a given secret.

When the secret used by the JWT sender and receiver is one and the same (shared secret, symmetric key), I understand how this works. All the inputs are identical, so the hash will be identical, whether calculated by the sender or receiver.

My actual question, and what I don't understand, is how this works when the secrets used by the sender and receiver are different (asymmetric keys, public/private key pair). I.e. if the hash produced by the sender was generated using the secret key, and the hash produced by the receiver (for signature verification purposes) was produced by the corresponding public key.

How can two different secrets yield the same hash?


texts: I'm trying to understand the KSA algorithm of RC4 which apparently scrambles the array which will later be used by the PRGA to generate the keystream. My question is, does the seed used by the KSA have to be kept secret?


texts:
I've been looking at the off-the-record messaging protocol, and there is something about its deniability property that seems strange to me.

Consider the following scenario:

  In the course of an OTR conversation, Alice decides to break Bob's deniability, e.g. she wants to be able to prove to
  some third party that Bob indeed sent one or more of the following messages without any
  way for him to plausibly deny the fact.

  According to the OTR protocol, Bob will publish his old MAC only as
  soon as he gets a positive confirmation of Alice having received his
  newest key by way of Alice using a newer key than the one associated
  with that MAC. This is so that Bob won't publish the old MAC before
  Alice can verify any messages in transit that are authenticated by it.

  But what keeps Alice from just ignoring all of Bob's newer keys starting at a certain point in the conversation,
  thereby making it impossible for him to discard any old key and also
  to publish any of the old MAC keys? If Alice were able to prove that
  she indeed never enabled Bob to publish the old MAC values, wouldn't
  that break his deniability?

Is there some safeguard against that attack, e.g. a timeout of
old keys, that encourages implementations to automatically publish
any remaining old MAC keys, even if the other party never
acknowledges their receipt or just leaves the conversation entirely?

Or is OTR messaging vulnerable against this (admittedly pretty specific) attack?


texts: A lower bound on the insecurity of CipherCloud?

texts:
CipherCloud claims to support , among other things, searchable encryption. A bunch of speculation seems to suggest they did this via some breathtakingly  incompetent means( unfortunately such speculation "appears" to be copyrighted)
Regardless of their actual methodology, if we assume their encrypted data is searchable by the cloud providers they work with without changes to the providers(e.g. salesforce), then doesn't this result for order preserving encryption constitute a lower bound on how insecure their system  could be(and a pretty poor one at that)?
The result deals with the security of the ideal functionality of an order preserving encryption (OPE) scheme.  This is the ideal model of a  scheme where you can sort  $c=enc_k(m)$ by numerical comparison of $c$. Any scheme where you search encrypted cipher texts with existing queries in a database must meet this requirement. This appears to suggest that the absolute best case for CipherCloud is that their encryption leaks roughly the $1/2m$ high-order bits of a given message* . This seems drastically unsafe for low entropy messages such as social security numbers, credit card numbers, earnings reports, and most other data you might want to search on in say a sales application.
*Per the paper, where M is the size of the message space(i.e. $M=2^l$ for $l$ length messages) "Intuitively, Theorem 4.2 implies that for $r\approx b \sqrt{M}$, where b is a large enough constant (say $b \ge 8$),there exists an adversary $A$ whose r-window one-wayness is very close to 1."


texts: Padding oracle attack, encrypting your own message

texts:
My understanding of the encryption attack on a padding oracle is that the attacker has a set of $P_i$'s and $\operatorname{Dec}(C_i)$'s

I understand that by back calculating the attacker can find out $C_{i-1}$'s because we have

$$P_i = \operatorname{Dec}(C_i) \oplus C_{i-1}$$

This way the attacker can find all the $C_{i-1}$'s, but what happens with the very last $C_i$? Since you're starting from the end and going backwards, it looks like the very last $C_i$ wont get calculated, in which case the attacker isn't able to encrypt all of the message...?

EDIT:

So i've run the decryption attack and obtained all the $Dec(C_i)$' for an intercepted ciphertext (so a bunch of blocks of $C_i$'s). and then using that i have calculated a sample $P_i$. I want to generate my own $P_i$ now and encrypt it. So what i've done is i take each block of my sample $P_i$ and XOR that with $Dec(C_{i-1})$ to get a C_i, however, the issue is that the response doesn't seem to be valid. So doesn't $Dec(C_i)$ directly depend on what $C_i$ is being passed into it? The conclusion i've made is that the $Dec(C_i)$ Value changes based on each block of ciphertext that's being fed into it, so the $C_i$'s that i generated using the previous $Dec(C_i)$'s won't be decrypted correctly, because the actual program computes a new set of $Dec(C_i)$'s and based on those my ciphertext isn't correct ... does that make sense? or am i misunderstanding the whole thing.


texts:
I understood the XOR trick that allows an attacker to guess a block of a previously sent message from the client to the server: the attacker forces the client to send the message $\tilde{m} = c_n \oplus m_g \oplus c$ where

$c_n$ is the last block of the last ciphertext;
$m_g$ is the attacker guess of the decryption of an arbitrary block of a previously sent message;
$c$ is the encrypted block that was chained with the real plaintext block $m$ (i.e., the one that attacker is trying to guess).

When the client sends $\tilde{m}$ to the server the result is

$$E_K(c_n \oplus \tilde{m}) = E_K(c \oplus m_g)$$

that is equal to $E_K(c \oplus m)$ iff the block $m = m_g$. Iterating this attack on all the blocks of a message $M$, the attacker can say if the message $M = M_g$.

So far, so good. What I can't figure out from now on, is how can he change his attack to decrypt a message, without doing a guessing attack. In particular, the problem is that if he tries to guess the block, he only has $2^{-64}$ (supposing to use a 8 byte block cipher) chance of success.

The articles that explain this second part of the attack say: "suppose you already know 7 byte out of 8, you only got a few more guessing to try ($2^8$)", but I don't understand how an attacker can know the first 7 byte of the block he want to decrypt.

As an example, this is an article that goes into the details of the attack. In the last part, he gives the following example

GET /index.html HTTP/1.1
Host: mysite.com
Cookie: Session=123456
Accept-Encoding: text/html
Accept-Charset: utf-8

How could an attacker find out the session number? This message would be encrypted as

GET /ind         ex.html         HTTP/1.1         \r\nHost         : mysite         .com\r\n         Cookie:          Session=         12345678
a7d25abbd67b2dbf e2ade7246ea5ed5 e99063ebe430b75b 746ae5eca36e2bc3 f6f62f99a076056f 6b14704973a779ae 7fa9300d4e490cba b6040b9542a59ad5 f9bb888ac3763722b

It's not clear (to me) how they achieved this result in the article.

Other resources that I've checked out are

BEAST attack confusion
https://www.slideshare.net/danrlde/20120418-luedtke-ssltlscbcbeast


texts: Role of Fermat's little theorem in the proof of correctness of ElGamal signature

texts:
In the Wikipedia article about the ElGamal signature scheme it is written, that Fermat's little theorem is used in the following proof of correctness:

From the signature generation in ElGamal we can derive, that:

$$H(m) \equiv xr + sk \pmod {p-1}$$

Then - the article states - Fermat's little theorem implies the following:

$$\begin{align}
g^{H(m)} &\equiv g^{xr}g^{ks}   &\pmod p\\
         &\equiv (g^x)^r(g^k)^s &\pmod p\\
         &\equiv (y)^r(r)^s     &\pmod p
\end{align}$$

The proof makes sense to me, i am just wondering, in what way Fermat's little theorem is used here, instead of just regular properties of exponentiation.


texts:
What is the most secure way to let Alice "input" her private key, transfer it to the server and decrypt the message? (Then destroy the private key on the server)

Every connection is using SSL.

Exmeple:

Alice log on the website. She have a new "email" from Bob. (Everything is stored in a database, it's not an actual email)

To read it, she needs her private key. How can she do that ? Upload it? Copy the key in a textbox and click submit? (May not be pratical for Alice) Store it on the server (Hugh security issue) ?

(And is it possible to suggest me some keywords please? I'm not used to Crypto.Stackexchange Thank you)


texts: How to prove truncated MD (or chop MD) hash function is collision resistant?

texts:
We have a collision resistant hash function (based MD construction) H with 2n bits hash value size.
Call chop(H) is a chopping n-bits from H's hash output.
How can I prove a chop(H) is collision resistant with n-bit?


texts:
While reading about Triple Diffie-Hellman, I was wondering how it can prevent MITM if the server decides to spoof key sets.

For example, Alice and Bob are connected using a server.

Alice ----- Server ----- Bob

What if the server, with malicious intention or under government request, tries to spoof the key sets? Is it possible to compromise the communication in such cases even using X3DH?


texts: RSA cracking: The same message is sent to two different people problem

texts:
Suppose we have two people: Smith and Jones.
Smith public key is e=9, n=179 and Jones public key is e=13, n=179.
Bob sends to them a message $M$.

The encrypted message $C_s$ to Smith is 32.

The encrypted message $C_j$ to Jones is 127

I tried to resolve this problem with no luck.

First I put both of them as an equation and tried to play with the module, multiplying and adding, but I can't retrieve the solution.
I know there is a way to resolve it but I haven't found it anywhere.

EDIT:
Is not a realistic situation. Is just for practice.
This is the primitive RSA. It has no padding.

I'm beginning to think that the problem is wrong maybe because the results I get are not correct.

This is the original problem text:

  Imagine that you are a CIA double agent. As good spy, you have discover that the agents Smith and Jones share the same modulo in their respective RSA public keys, namely ($e_s$ = 9, n = 179) and ($e_j$ = 13, n = 179).
  After some days sniffing the network, you see that the CIA director has sent the same message m to both
  agents. Concretely he has sent $c_s$ = 32 and $c_j$ = 127. Can you recover the original message m?.

    Solution m = 10

Resolution by me:

So I have the following equation:

$c_s$ = $m^9$ $mod$ 179

$c_j$ = $m^{13}$ $mod$ 179

And I began to use the extended Euclidean algorithm:

9*$a$ + 13*$b$ = $gcd$(9,13)
which gives me:

$a$ = 3 and $b$ = -2

As $b$ is negative, we calculate:

$i$ $=$ $c_j^{-1}mod179$

the inverse of $c_j$ (127) which is $-31$

And finally:

$M$ = $c_s^a$ * $i^{-b}$ $mod$ n

$M = 32^3*{-31}^2$ $mod$ $179$ $=$ $10$

Great! thanks!!!


texts: Are biases narrowed towards the provenance of hard NP complete problems relevant?

texts:
I hear of randomized reduction, deterministic reduction and non-deterministic reduction of complexity from A to B problems. This could make things impossible for polynomial time adversary prying into NP - hard problems.

Are these biases in complexity what makes the computation infeasible if a problem cannot be solved in polynomial time?

Does it matter really, whether a problem' solution is bounded and affirmed in a deterministic turing machine or non-deterministic turing machine?

Is it not plausible that to achieve the right cryptosystem to serve us another 100 years a vital consideration must be giving to a mix of all these reduction in polynomial time within a scope or formation of naturally existing context. e.g lattice or their matrix images?

FYI
Please think about quantum resistant possibilities as you answer these questions. A good crypto scheme will give rise to a data stream that will bear no information but a verifier could still validate a prover without knowing much of the secret there in.

[AJI04] Miklos Ajtai. Generating hard instances of lattice problems. Quaderni di Matematica, 13:1–32,2004. Preliminary version in STOC 1996. – Jossy J. Umezurike 2 mins ago

[AKS] M. Ajtai, R. Kumar, and D. Sivakumar,A Sieve Algorithm for the Shortest Vector Problem, Proc.33rd Symp. Theory of Computing (STOC), pp. 601–610, 2001
https://github.com/jumezurike/backend-master-lokdonSKI/blob/master/README.md
https://www.cs.uml.edu/~wang/acc-forum/avg/avgnp/node29.html

http://www.cs.toronto.edu/~sacook/homepage/1971.pdf


texts: What does it mean exactly that an adversary can control a polynomial number of parties?

texts:
I have an intuitive idea of this, but I am not sure if I am formally interpreting it correctly. In the scenario I am considering, each party is identified by a sequence of $n$ bits and I have $2^{n}$ parties.
If I say that an adversary can control a polynomial number of parties, what does it mean formally? Is it with respect to $n$, $2^{n}$ or what? How do you explicit it as a function?

My idea is that, since the number of parties is exponential with respect to $n$ (in particular, it is $2^{n}$), then, saying that the adversary controls a polynomial number of parties means that it controls a number of parties that is polynomial with respect to $n$. It can be $2 \cdot n$, $n^{2}$ or any polynomial function of $n$ (it should be possible to express it in general as $poly(n)$).

Is this correct?


texts: Why in the Rao-Nam private key version of McEliece scheme, P matrix is multiplied after adding error vector?

texts: The private key version of McEliece known as Rao-Nam scheme, the encryption is done as c = (mSG + e)P. What is the need for applying permutation matrix on the error vector?


texts: Calculate multiplication of a cipher matrix and a plain matrix

texts:
There is a matrix $A$ that we don't want to be revealed, and there is a matrix $B$ that is known. Is there any way to calculate $A \times B$ without revealing $A$?
$A$ can be encrypted. But we don't want anyone to know it, but we want anyone to be able to calculate the multiplication of it to another matrix.
Is there anyway to do such a thing?


texts: Why does KangarooTwelve only use 12 rounds?

texts:
The initial Keccak submission used 18 rounds, which was bumped up to 24 rounds for the final version after distinguishers were found for a reduced 16 round variant.  However, the Keccak team has recently released a spate of cryptographic primitives based on a twelve-round variant of Keccak.

I've seen scattered references which give the impression that new bounds were found and that even 18 rounds is overkill.  However, I can't grok the research and I need a canonical answer.

What led them to feel comfortable with 12 rounds for K12?


texts: How many different ciphertexts in repeated substitution cipher?

texts: Consider an alphabet with 26 letters. Then a substitution cipher has $26!$ possible ciphertexts (with every letter substituted). What about repetive substitutions on a 5 letter word for example? How many different ciphertexts will result? Like $\sigma(a)=b, \sigma(b)=c, \sigma(c)=a$, then $abc \rightarrow bca \rightarrow cab \rightarrow abc$ so two ciphertexts for $|A|=3$.But what about generally?


texts: Can I use modulo $n^2$ arithmetic where $n=p \cdot q$ for ElGamal encryption?

texts:
In the paper which I was reading, the authors were using ElGamal encryption with modulo $p$, where $p$ was a prime.

Do the commitment properties still hold if we use modulo $n^2$ where $n=p \cdot q$ and $p$ and $q$ are large primes?

I was asking this because a number of other commitment schemes use modulo $n^2$ arithmetic.


texts: Cryptographic scheme where a single message cannot be decrypted but if combined with other it can be

texts:
i'm wondering if this type of cryptographic scheme does exists. I know about homomorphic encryption but if one has the private key, he can decrypt every single message.

I would like to know if there is a scheme where each user can encrypt the message with a key (public?). Then, the one who has the decrypiton (private) key cannot decrypt every single message but if the messages are combined together (such as muliplied or summed), he can get the correct result.

For instance: A has a key KA, B has a key KB. A encrypts the value 1 with the key KA and obtains MA. B encrypts the value 2 with KB and obtains MB. MA and MB are published. An element C has a decryption key but he cannot decrypt MA and MB but if they are combined, such as MA+MB, he can decrypt the result and obtain 3 (1+2). I think if this type exists maybe there are several public-private keys related in a certain way...


texts: How to solve this decryption algorithm given the encryption algorithm?

texts:
Consider the following cryptosystem with plaintexts from the set $M$ and ciphertexts from the set $S$ with $M = S = \{0, 1\}^4$ . A plaintext $P = (P_1, P_2, P_3, P_4)$ is encrypted to a ciphertext $C = (C_1, C_2, C_3, C_4)$ as follows.
$C_1 = (a P_1 + P_2) \pmod 2$
$C_2 = (b P_1 + c P_2) \pmod 2$
$C_3 = (d P_3 + e P_4) \pmod 2$
$C_4 = ( P_3 + f P_4) \pmod 2$
The key is given as $k = (a, b, c, d, e, f)\in \{0, 1\}^6$, i.e., it holds $C = E(k,P)$.
a. Describe the decription algorithm.
b. Is the given system perfectly secure? Prove your answer.

I know that if $C_1 = a + P_1$ then $P_1 = a + C_1$. However because $C_1$ and $C_2$ use the same letters $P_1$ and $P_2$ (also in the case of $C_3$ and $C_4$), I don't know how to reverse them to get back $P_1$ and $P_2$


texts: Logjam: "composite order subgroups" explained for TLS developers and system admins?

texts:
I have read the recent logjam paper Imperfect Forward Secrecy:
How Diffie-Hellman Fails in Practice.

On page 11 in the Recommendations section, they state:

  Avoid fixed-prime groups In the medium term, employing
  negotiated Diffie-Hellman groups can help mitigate some
  of the damage caused by NFS-style precomputation for very
  common fixed groups. A current IETF draft [18] proposes
  a negotiated group extension to TLS. However, we note
  that it is possible to create trapdoored primes [43] that are
  computationally difficult to detect. At the very least, primes
  should be checked to be safe primes, or groups should use
  a verifiable generation process such as the one proposed in
  FIPS 186 [37], and the process for generating primes within
  the TLS session should be fixed so as to thwart the risk of
  trapdoors.

While this is lighter on the math than the section Attacks on Composite-Order Subgroups, I still don't know what that means in terms of implementations, algorithms, and libraries.

Further down that page they also state

  A key lesson from this state of affairs is that cryptographers
  and creators of practical systems need to communicate better.

So, as a software guy working on a project which involves in-house implementations of TLS, I would love for a mathematician / cryptographer to explain to those us without group theory backgrounds  (if possible) what is mean by "choosing safe primes", and choosing a generator $g$ which "generates a group with at least one sufficiently large subgroup order" (pp. 6, Attacks on Composite-Order Subgroups), and what that means for the code that I write, algorithms I implement, and libraries that I call. A layman's explanation, or pointers to group theory-related algorithms for generating DHE parameters would be great.


texts: Why do we use Generlized Forking Lemma with several crucial points, while in the security proof we just rewind to a single point

texts:
Recently I have been reading this paper by Dan Boneh et al., where the authors are going to use  a general form of forking lemma, to prove the security of their Schnorr multi-signature.
As I understood, this general form of forking lemma is about having several crucial points, rather than a single point (by crucial I mean the point that we rewind the adversary).
When you go to the security proof (pp 21-22), what they are using is just rewinding to a single point.
So I was wondering what is the reason for using this general forking lemma?


texts: How can I store a combination of multiple pass phrases?

texts:
Let's assume we have 2 phrases, one is the real password from a user, and the other is generated from the real password and almost impossible to guess. You would need both to authenticate a user. What would be the best theoretical way to store them, or how to encrypt them so that if attacker somehow gets encrypted pass phrase wouldn't be able to decrypt both phrases? I know with brute force, attacker can eventually break the encryption, but what would be best to do to not make it easier for attacker to break it?:)

If we encrypt (with symmetric algorithm) them separately and store them somewhere (doesn't really matter where), first phrase could be vulnerable to dictionary attack. We could combine them, for example p1f1p2f2… (phrase1=p1p2p3…, phrase2=f1f2f3…) and then encrypt them. That way the combined phrase shouldn't be vulnerable to dictionary attack, and attacker could only use brute force.

But I'm not sure how the way we combine them affects encryption algorithm. Is there any specific encryption algorithm that would be better than the other? Could there be vulnerabilities regarding how we combine them, because they could get discovered if we statistically analyse many examples of encrypted combined pass phrases (I'm guessing here)?

Or is there no way to know before actually analysing the algorithm, encryption algorithm and encrypted pass phrases?


texts: Proof that a encrypted file has the same content as an (existing) original

texts:
Assume that Alice has a file F which she is going to send, in encrypted form, to Bob. Alice possesses F and the public encryption key K of Bob in form of an X509-certificate.
She generates the file E using the encryption algorithm CNT_3DES, BitsInKey = 192 (RSA PKCS#1 encryption method).
She sends to Bob the file E through a certified mail system which will get a digital signature and a time stamp from an external authentication authority. Therefore it is possible to include in the body of the mail any information, including hash codes, that will be accepted as well known before the creating time of the mail.

After some time Alice has to proof to Mike that the file E send to Bob has the same content of the file F. But Mike does not have the private key of Bob for decrypting the file. And encrypting the file F now produces a different file than E since encryption adds a random padding on encryption stage. How can this proof be given from Alice to Mike?
As explained, it is possible to include in the body of the mail any useful information that will be necessary for this proof.

I hope that I explained my problem in a sufficiently clear way. And sorry for my poor English.


texts: Weakness in using only one RSA key pair for two-way communication?

texts:
In Alice/Bob/Cindy terms (EDIT: and with a little more detail):

Alice and Bob have each securely obtained one key of an RSA keypair from a trusted third party. Alice has one key ($e$ and $n$), Bob has the other ($d$ and $n$, where $d\equiv e^{-1} (mod\ \phi(n))$).

The RSA algorithm technically does not care which of the two keys is used to encrypt and which to decrypt; if $c_1 \equiv m^e (mod\ n)$ and $m \equiv c_1^d (mod\ n)$, then $c_2 \equiv m^e (mod\ n)$ and $m \equiv c_2^d (mod\ n)$. ($c_1 \neq c_2$)

Therefore, Alice uses $e$ and $n$ to encrypt a message $m_a$ into ciphertext $c_a$ and sends it to Bob, who decrypts it with $d$ and $n$, then encrypts his response $m_b$ with the same $d$ and $n$, and sends the ciphertext $c_b$ to Alice who can decrypt it with $e$ and $n$. Thus, one pair of asymmetric keys is being used to form a two-way communication channel, instead of the normal one-way usage.

Now, Cindy does not know $e$, $d$, or $n$, or any artifact used to produce them, such as $p$ and $q$. she can only see $c_a$ and $c_b$ as they are passed between Alice and Bob. Given that all other security concerns with RSA are properly handled, such as $\geq$2048-bit keys and OEAP padding scheme, is there an "efficient" way (an attack) by which Cindy can obtain $m_a$ and/or $m_b$?


texts: How did the Koblitz/Menezes papers affect the cryptography community?

texts:
Two highly-critical papers by Koblitz and Menezes (two well-regarded mathematicians who've contributed to the crypto community) were published years ago: Another Look at “Provable Security” in 2004, Another Look at “Provable Security”. II in 2006.

Have these papers had any noticeable impact on how research is conducted in the provable-security community?  Or have these papers largely been ignored?


texts: Does the output of a cipher have to be no longer than the input?

texts: I have recently been playing around with cyphers and creating some simple ones to practice and improve my programming skills, and I recently created a cipher which in my opinion is very complex and secure, even utilising binary, and then I started to wonder whether or not my cipher could actually be used, so after doing a little bit of research I found out that, apparently, a cipher isnt good unless its the same length as the original? so if you input "password" my cypher outputs "[.##4959#12#41#8#{20", a very complex algorithm is used here, and my idea was that this cipher would be used with short pieces of text/numbers, like passwords or bank account numbers. so is my cypher useless?


texts: Attacking hashed password by timing attack and other means

texts:
This question is inspired by this recent one, which raises a point that need to be made quantitative to be meaningfully discussed. I chose an unusual approach: a new question worded as homework that could be asked in a computer security with applied cryptography class (please use meta for critics of that method).

Some system keeps track of user passwords as (userID, H) pairs with H of 20 octets and a single pair per userID. To test an alleged Password for some userID, it is checked that some (userID, H) exists; then computed D of 20 octets as
   PBKDF2(PRF = HMAC-SHA-1, Password, Salt = userID, c = 10000, dkLen = 20);
then the alleged Password is accepted according to the C expression memcmp(D, H, 20)==0.
The value of c is 10 times what is described to be a significant burden for opponents in RFC 2898 defining PBKDF2.
The documentation of memcmpstates:

  int memcmp(const void *s1, const void *s2, size_t n);

  The function compares successive elements from two arrays of unsigned
  char, beginning at the addresses s1 and s2 (both of size n), until
  it finds elements that are not equal:

  If all elements are equal, the function returns zero.
  If the differing element from s1 is greater than the element from s2, the function returns a positive number.
  Otherwise, the function returns a negative number.

Assume than an adversary

can submit (userID, Password) pairs and determine if that's accepted or not, at a rate of $r\approx2^{10}$ pairs per second;
can at every such attempt measure the running time to fine accuracy, and consistently deduce how many elements have been compared in memcmp;
can perform PBKDF2 at a rate of $h\approx 2^{40}$ per second (less computing power than devoted to bitcoin mining according to this statistic);
does not initially know any H;
gets hold of $n\approx16$ target userID.

Give some approximation (as a function of the parameters) of the expected wall clock time since (5) for a competent adversary to find an acceptable (userID, Password) pair, without and with the insight given by (2), for these two models of choice of Password:

uniformly at random among $2^b$ for $7\le b\le90$; detail the adversary's strategy when $b\approx44$ per XKCD recommendation;
by user, with $u\approx 1/4$ of users having picked a password that occurs at least $5$ times in a list known to the attacker, comprising password choices assumed about representative of how actual users choose passwords, with statistics per these 2040 lines of the form a*b (or just a when b is $1$), each line meaning that b distinct password choice(s) each occur a times in the list (note: the threshold of $5$ keeps $\approx50\%$ of the $32603388$ choices, and $\approx4\%$ of the $14344391$ distinct choices).

Propose C code for a memneq function, usable as replacement of memcmp where sign of its result is immaterial, and likely to close the timing vulnerability.

Outline standard techniques to dramatically improve security with no change of the current passwords.


texts: pwd-hash like algorithm which can be computed on paper

texts:
"Common password problem" is well known problem, when user uses one password for many resources (web sites, logins to computers, etc...) For example, if one web site loses it' database, which contains user passwords and emails, somebody when might try to use this password on other sites and come to success...
To solve this issue pwdhash exists. This is good solution, only problem is, that user needs special software to compute the password for each web site, for example. So user needs some reliable software for this. User should be sure, that this software doesn't remembers and transfers to somewhere in network entered main password. User should be sure, that this software can't be imperceptibly replaced with malicious version of program that is indistinguishable from the original. For example, it's hard to trust to "pwdhash" application from Google Play market (because it is issued by unknown person and might be silently updated in future). Also it's hard to trust to original "pwdhash" web site, because it might be replaced in some moment of time. Moreover, web site might be just inaccessible.
To solve "common password problem" I want to use some sort of one way hash, which can be computed by hands, on sheet of paper, or even can be counted in mind. I understood, that this might be not strong cryptographic hash, but from other side, I can completely trust this method.
Suppose I have service name, for example "booking" (.com). I want mix it with some permanent password, lets suppose this will by my name "kirill", and I will get password which I can use for login to "booking.com" website.
At first, I will translate name of service and permanent password to numeric form. To do this, I will use telephone keypad layout. So translation will be following:

"booking" = 2665464
"kirill" = 547455

Then I compute: $R = N * 1000000 \bmod S$, where $N$ is name of service encoded in numberic form, $S$ is my permanent password in numeric form. And $R$ is resulting password, which is valid only for some particular service.
I will get:

R = N % P * S = 2665464 * 1000000 % 547455 = 64052235

Now I translate $R$ back to alphanumeric form, again by using telephone keypad. First time i selecting first letter for each corresponding digit (zeros and ones i can't tranlate, so i leave it as is). So I will get:

314715 = "M1gp1j"

Also I will make the first letter capital (many services require to mix capital and lowecase letters). And in case, if resulting string doesn't contains any digits, I will leave last digit as is (again, some services require to include digits in passwords).
So, I get password, which is unique for each service and looks like randomly selected characters. And it's hard to reverse it, to get my permanent password (547455 or "kirill"). Of course, for practical purposes length of my permanent password should be longer, more than 8-10 characters.
This is good or bad method?  And why?  And how this method can be improved?
Links:


texts:
Cycles per byte seems to be a critical concern in designing and choosing stream ciphers. For example, from Wikipedia, RC4 has 7 cycles/byte on original Pentium chips.

How is this calculated? Do they just time the encryption of multiple megabytes and then divide by the CPU's clock speed? Do they look at the assembly code and lookup cycle per instruction in some table, figuring in pipelining, branch prediction, etc.?


texts: As the final permutation of the Feistel function is the inverse of the initial permutation, it undoes the initial permutation.So how is this helpful?


texts: A doubt about Diffie-Hellman Key Exchange

texts:
I have a doubt about the Diffie-Hellman problem:

Is it possible to send a message to someone using only the Diffie–Hellman key exchange?

Since it's called a key exchange can you only make a key?


texts:
I use HMAC(ciphertext)+ciphertext for authenticated encryption.

The same key is used for both MAC and encryption.

Is that right? Is using separate keys for MAC and encryption necessary or any good?

I ask this beacause I have read somewhere that keys used for one role shouldn't be used for the other role.


texts: Conditional probability being Constant in Threshold Cryptography

texts: I am working on Threshold implementation of algorithms to prevent side channel attacks. I am not that much proficient in Statistics and Probability theory. I want to know what is the significance of conditional probability being constant...?! Please help me in understanding...


texts: PAN authenticatable irreversible tokenization algorithm

texts:
I need to implement algorithm to create authenticatable irreversible tokens from PAN, without using any secrets.

Is it possible? Is there any standards for that from associations?

I was thinking about HMAC but it needs to distribute secret symmetric key to all relevant parties. How to do it without distributing cryptographic key? Also it should prevent to create an oracle.


texts: Proxy Re-Encryption with provable re-encryption target

texts:
Suppose Alice has encrypted some plaintext $P$ to Bob. Bob wishes to re-encrypt this information to Charlie via proxy, in such a manner that:

The proxy cannot obtain $P$
The proxy can prove that Bob has provided a valid re-encryption key, meaning that Charlie will be able to obtain $P$ by decrypting with his private key
The proxy can prove that the ciphertext originated from Alice

Is such a scheme possible?


texts: I am new to AES and I am too much confused about the generation of S-box in AES. I don't have any idea of $GF(2)^8$ field and how the things are happening around. Please answer this question with a example in layman language.


texts: Relationship between source and output entropy

texts:
True Random Number Generator (TRNG) use external physical phenomena to generate true randomness. I have a TRNG which uses two sources (oscillators) and gives an output of 256 bits. The entropy of TRNG output is 256 bits. The entropy of bit string with N distinct possible combinations is given by log2(N) bits (reference is given below). TRNG claims to have entropy of 1 bit for each input source i.e. totally unpredictable. Is there any relationship between TRNG’s source entropy and output entropy ?

http://csrc.nist.gov/publications/drafts/800-90/draft-sp800-90b.pdf

Any help/reply is appreciated please.

Thanks & Regards,


texts:
I understand that most stream ciphers, due to being applied with a simple XOR, are specially fragile against data tampering, and must be used with some MAC mechanism. So I am investigating the use of UMAC for this purpose.

I also understand that UMAC works by XORing an universal hash function based on a secret key with a pseudo-random number generated with AES and a nonce:

$ Tag = U_{k1}(M_{clear}) \oplus AES_{k2}(nonce)$

The thing is: since I already have my stream cipher setup, can I just take hash $H_{k1}(m)$ and encrypt it by XORing with the pseudo-random output from the stream cypher plaintext, the same way done with the plain text?

$M_{wire} = (M_{clear}||H_{k1}(M_{clear})) \oplus CipherStream_{k2}[i..(i+len)]$

Is there any problem with this approach? Or a block cipher was chosen for some specific need?

Also, I have suggested applying the hash to the clear-text; does it make any difference applying it to the cipher-text or to the clear-text?


texts: Does having an SHA256 hash compromise PBKDF2 secrecy?

texts:
If I have a password pwd, and I hash it with SHA256 and send it to a server for authentication (server will apply bcrypt for storage), and then I use PBKDF2-SHA256 with a large number of iterations to derive a key for decrypting user data, does the fact that the server knows the original SHA256 hash or the bcrypt hash allow it to derive the original pwd or the decryption key?

Another way to phrase the question: see below pseudocode

CLIENT:
hash1 := SHA256(email + pwd)
> send hash1 to server

SERVER:
hash2 := bcrypt(hash1)
if hash2 == stored expected value; send data and salt back to client

CLIENT
key := pbkdf2(email + pwd, salt, ...)
AES.decrypt(data, key)

In my scenario, the SERVER is a third party. If, say, the server went rogue and tried to steal all of the users' data, would the server be able to do so easily, knowing about the contents of hash1 and salt?

  P.S.: Does 5 million iterations somehow weaken PBKDF2 (hash cycles, etc.)?


texts: Decryption of message in IBE without random oracle using bilinear pairing registration?

texts:
I find the following IBE scheme from the videos posted and i don't understand the decryption algorithm, will any one please elaborate  the  6th step

scheme

Setup($\lambda$)  :     $(\mathbb{G}, \mathbb{G}_T, g, P)$   <-- GenBilgroup($\lambda$)

$\alpha\leftarrow_R\mathbb{F}_p$
Public Parameters :   $pp = [ g , y = g^\alpha  , g_1, h ] \in \mathbb{G}$
Master secret : $mk = g_1^\alpha $
Keygeneration:  $k(mk,id)$: $d_1= mk\cdot(Y^{id\cdot h})^r, d_2 = g^r $
where   $r\leftarrow_R\mathbb{F}_p $
Encryption: $E(pp,id,m)$ :  $c_1 = g^s, c_2=(Y^{id\cdot h})^s, c_3=m\cdot e(y, g_1)^s$
Decryption: $e(c_1,d_1)/e(c_2,d_2)$ will give $e(y,g_1)^s$  How?
             and $m$ is obtained by dividing $c_3$ by that value.


texts: How to use CRT to compute 4 square roots while decryption in Rabin Cryptosystem

texts:
I'm reading Rabin Cryptosystem which requires to compute 4 square roots $r, -r, s,- s$ while decryption of cipher text $c$ such that

$$r = (y_p \times p \times m_q + y_q \times q \times m_p) \mod n $$
$$-r = n - r $$
$$s = (y_p \times p \times m_q - y_q \times q \times m_p) \mod n $$
$$-s = n - s $$

$m_p = c^{\frac{1}{4}(p+1)} \mod p; \, \,m_q = c^{\frac{1}{4}(q+1)} \mod q; \, \, y_p \times p + y_q \times q = 1$

I'm not getting, how we can compute $r, -r, s,- s$ using Chinese Remainder Theorem.


texts: What are fixed points and length extension attack in hash functions?

texts: I was recently reading about hash functions, and I came across fixed points (one or more fixed points, interested in both) and length extensions, but I didn't exactly understand how these work. If someone can explain them or point me to a reference, I would be glad.


texts:
I am trying to implement ElGamal in java without using the in-built libraries. The problem occurs when I am trying to find the generators of the number(in this case 11). Everything works perfectly except that it is returns 10 as a valid generator of 11(which it is not, right?)

public void generateKey()
{
    SecureRandom r = new SecureRandom();
    BigInteger i ;
    //i = new BigInteger(2048, certainty, r);
    i = new BigInteger("11");
    ArrayList<BigInteger> numbers = new ArrayList();
    boolean safePrime = isSafePrime(i);

    numbers = zGenerator(i, safePrime, 10);

    System.out.println(numbers);
}

public boolean isSafePrime(BigInteger i)
{
    return i.subtract(BigInteger.ONE).divide(new BigInteger("2")).isProbablePrime(90);
}

public ArrayList<BigInteger> zGenerator(BigInteger i, boolean safePrime, int count)
{
    Set<BigInteger> numbers = new TreeSet<BigInteger>();

    if(safePrime)
    {
        BigInteger num = new BigInteger("2");
        BigInteger exp = i.subtract(BigInteger.ONE).divide(new BigInteger("2"));
        do
        {
            if(num.modPow(exp, i).compareTo(BigInteger.ONE) > 0)
                numbers.add(num);
            else
                numbers.add(num.negate().mod(i));
            num = num.add(BigInteger.ONE);
        }while((--count > 0) && (num.compareTo(i) < 0));
    }

    return (new ArrayList<BigInteger>(numbers));
}

Output: [2, 6, 7, 8, 10]

I even tried using $g^q=p-1 \bmod p$


texts: Memory-hard operations in work-factor hash functions

texts:
I'm playing around with work-factor hash functions, and I'm looking for a memory-hard operation to make it resistant to GPU / parallel hardware attacks. I considered a very large (i.e. 64K) s-box that gets shuffled based on the state per round, but I have a feeling that there are ways to optimise such an operation for minimal memory usage.

My current best scheme is as follows:

state = pass
while(length(state) < 32768)
{
    state += sha512(state);
}

Is such a scheme guaranteed to require a lot of memory, or can it be optimised? I know there are tricks to reduce memory usage when computing hashes. Are there other simple operations that provide such guarantees?


texts: P = NP and current cryptographic systems

texts:
I've recently heard some people claiming that if the fact that P = NP is proven, most (all?) the current cryptographic algorithm considered secure like RSA will be unusable in secure systems.

My question is :

1. If P = NP is proven TODAY, will a RSA key (let say 3072 bits) be still enough to ensure a certain amount of security.

2. If not, what could we do to have at least the same amount of security (take a larger key length? a stronger algorithm?)


texts: For a random permutation $P$, what's the probability of the following event?

texts:
For a random permutation $P$ and $q$ distinct inputs $x_1,\ldots,x_q\in\{0,1\}^n$, what's the probability of the event that there exists at least one collision among $\{P(x_1)\oplus x_1,\ldots,P(x_q)\oplus x_q\}$?

Note: I have tried to compute this probability, but it is quite hard for me to obtain the result, either for the exact probability or the lower bound of this probability. The following is my attempt to solve this problem when $q=2,3$.

Denote by $\mathsf{E}$ the event that there exists at least one collision among $\{P(x_1)\oplus x_1,\ldots,P(x_q)\oplus x_q\}$.

If $q=2$, it is easily seen that $\Pr[\mathsf{E}]=\Pr[P(x_1)\oplus x_1=P(x_2)\oplus x_2]=\frac{1}{2^n-1}$

If $q=3$, we have 3 random elements $P(x_1)\oplus x_1,P(x_2)\oplus x_2,P(x_3)\oplus x_3$. We focus on computing $\overline{\mathsf{E}}$ the complementary event of $\mathsf{E}$:
 \begin{align}\Pr[\overline{\mathsf{E}}]=&\Pr[P(x_1)\oplus x_1\neq P(x_2)\oplus x_2 \wedge P(x_1)\oplus x_1 \neq P(x_3)\oplus x_3 \wedge P(x_2)\oplus x_2 \neq P(x_3)\oplus x_3]\\
=&\Pr[P(x_1)\oplus x_1 \neq P(x_3)\oplus x_3 \wedge P(x_2)\oplus x_2 \neq P(x_3)\oplus x_3\mid P(x_1)\oplus x_1\neq P(x_2)\oplus x_2]\cdot\Pr[P(x_1)\oplus x_1\neq P(x_2)\oplus x_2]

\end{align}
Without loss of generality, assume that the value of $P(x_1)$ is fixed. There are $2^n-1$ possibilites for $P(x_2)$. Conditioned on the event $P(x_1)\oplus x_1\neq P(x_2)\oplus x_2$ happening, the probability of the event $P(x_1)\oplus x_1\neq P(x_3)\oplus x_3\wedge P(x_2)\oplus x_2\neq P(x_3)\oplus x_3$ may change according to the choices of $P(x_2)$:

If $P(x_2)=P(x_1)\oplus x_1\oplus x_3$ or $P(x_2)=P(x_1)\oplus x_2\oplus x_3$, then the probability of the event $P(x_1)\oplus x_1\neq P(x_3)\oplus x_3\wedge P(x_2)\oplus x_2\neq P(x_3)\oplus x_3$ is $\frac{2^n-2-1}{2^n-2}$.
If $P(x_2)\neq P(x_1)\oplus x_1\oplus x_3$, $P(x_2)\neq P(x_1)\oplus x_2 \oplus x_3$ and further $P(x_2)\neq P(x_1)\oplus x_1\oplus x_2$, then the probability of the event $P(x_1)\oplus x_1\neq P(x_3)\oplus x_3\wedge P(x_2)\oplus x_2\neq P(x_3)\oplus x_3$ is $\frac{2^n-2-2}{2^n-2}$.

Hence,
\begin{align}
\Pr[\overline{\mathsf{E}}]=&\frac{2}{2^n-1}\cdot\frac{2^n-3}{2^n-2}+\frac{2^n-1-3}{2^n-1}\cdot\frac{2^n-4}{2^n-2}\\
=&\frac{2^{2n}-6\cdot 2^n+10}{(2^n-1)(2^n-2)},
\end{align}
and $\Pr[\mathsf{E}]=1-\Pr[\overline{\mathsf{E}}]=1-\frac{2^{2n}-6\cdot 2^n+10}{(2^n-1)(2^n-2)}$.
For $q\ge4$, the computation is complicated and I haven't found a good method to tackle it.


texts:
In our current system we use an encryption solution based on RSA with OAEP padding. Key size is optional but default 2048. What is the general strength of RSA with OAEP? Are there know attacks that can break it, their complexity? Are people using it and relying on it as secure enough?

Thanks


texts: If cryptographic hashes are completely unique, could they theoretically be used to transfer data?

texts:
I know it sounds ridiculous, but hear me out. We know that good hashing algorithms would generate hashes that are pretty much unique. If, in the future, we create a perfect (or just really near perfect) algorithm, could those hashes be used to represent larger chunks of data in a totally unique way? If they truly were unique and determined entirely by the file, could a powerful enough machine work backwards and reconstruct the file?

Now, this is a bit of a stretch from what we currently know, but I'd think it might be possible. Quantum computers can perform many different tasks at once, and we know that they pose a significant threat to modern forms of encryption because of this ability. While that isn't exactly the same thing as guessing every possible file that could've produced a particular hash, but I'd imagine there might be a way to make the process more efficient.

Maybe you get a hash that's a couple kilobytes long, allowing for billions of different input types. Combine that with a computer capable of generating and testing every possible input simultaneously and you'd be able to send tons of information in a couple kilobytes of transmission.

I'm not asking if it's possible to do with our current technology, as I'm fairly sure it isn't. I just want to know if the process of hashing a file could (in theory) support it.


texts: I know that when the domain is  $\{0, 1\}^{m}$ in  function $h(x)=Ax$ for $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}$, this function is called  Ajtai hash function. So when the domain is extended to $\mathbb{Z}_{q}^{m}$, is it also called Ajtai hash function?


texts: Importance of the order of public/private key application to a signed encrypted message

texts:
Let's say two users (U1, U2) each have a private key they keep to themselves, and each broadcast a corresponding public key to the world.

Let's then say that U1 wants to send a signed encrypted message to U2. I understand the idea that U1 wants to encrypt the message using his own private key, so that U2 can have proof that the message indeed came from U1 (since if U1's public key can decrypt a msg, it must've been encrypted by U1), and also U2's public key, so that only U2 can decrypt the message using his private key.

What I'm not completely clear on are the differences between first encrypting with U1's private key and then U2's public key, or in the opposiste order.

The way I see it, in the first possible order (U1 private, then U2 public),
nothing can be gleaned from the doubly encrypted message by observers, even if they have both U1 and U2's public keys.

If U1 were to doubly encrypt the message in the opposite order (using U2's public key first and then U1's private key), the only difference would be that observers would be able to break the layer of U1's encryption (using his public key) and see that he sent a message (but not to whom, or at least not from decrypting that first layer). Nothing more could be observed because the decrypted message (using U1's public key) would just reveal another layer of encryption that only U2's private key could decrypt.

Is that correct? Does order matter other than that?


texts: Why was the Navajo code not broken by the Japanese in WWII?

texts:
In reading about this topic recently, to my understanding, the encryption schemes used on top of the Navajo language were very simple and definitely could have been broken (my research shows they mapped Navajo words to various different meanings).

The Navajo language alone is obscure, had few speakers, and was not a written language - but still I'm amazed that the code was never broken. Isn't this an example of "Security through obscurity"?

No matter how obscure the language was, the sounds still mapped to English phrases at the end of the day. Through cryptanalysis, shouldn't the Japanese have broken the code? Am I missing something here, or is this an example of security through obscurity actually working?

Edit:
Follow up question: Could a similar scheme work today?


texts:
Can somebody analyze this scheme and explain how (in?)secure it is?

Assume that:

The keys were initially securely exchanged
All keys are truly random

In this scheme:

The key size is of length 2s, the plaintext is of length s, and the total message size is 3s
The first 2s contains a randomly-generated key to be used for the next message
The last s contains the plaintext.
The message in question uses the Vernam cipher
The first half of the key encrypts the next key, and the last half encrypts the plaintext

How secure is it to have every bit in the first half of the key (total size s) encrypt every two bits of the next key to be used?

Does this leak information about the keys?
Is it possible to actually deduce keys from that?

What if some sort of random mapping where each bit of the key does not encrypt consecutive bits of the next key was thrown into the mix?

Edit:

Example message layout:

|     Next Key(size 2s)        |   Plaintext(size s)  |
               |
               |^ This half is the key for the next plaintext
^ This half is used to encrypt the whole key (each bit encrypts 2 bits of the next key)

Edit 2:

Message: | Next Key Key | Next Key | Plaintext |
           ^Encrypts this-\/     ^Encrypts this-\/
 Possible Random Mapping->\/                    \/
              [_________________________]       \/
Next message: | Next Key Key | Next Key | Plaintext |

What is inherently insecure about each bit of a random key encrypting two bits of the next (entirely random) key in this scenario?

In addition, would adding a random mapping between the bits of Next Key Key and the next key add any security if the mapping was changed every message (some kind of mapping struct in the plaintext)?

If not, why? If this scheme is completely insecure, I wish to understand in what specific ways it may (as you say) leak information about the plaintext.

Edit 3:

Upon inspection, it turns out that one only needs to figure out HALF of the first key in order to crack the entire message chain. Each message makes it easier to find that half-key, since each message depends on the previous one.