Wednesday, 24 August 2016

A weak password yet strong encryption


Suppose Alice wants to encrypt a secret message "hello" and pass the ciphertext (the encrypted message) to Bob who decrypts and reads the original message. Alice and Bob use a shared password "john" to encrypt and decrypt. Alice and Bob do not want Eva to read the message, but they are aware that Eva knows how to decrypt the message and learns the ciphertext. What Eva does not know is the password "john". However Eva has a hackers dictionary of a million passwords including "john"; and she can try each password from the dictionary in a hope to decrypt the message. If decryption is fast, then trying all million passwords is not a big job. Can Alice and Bob make sure that Eva is not able to decrypt and read their secret message?

There are two possible solutions. One is to use a complex password e.g. "john34xrvq968b"'. But Alice and Bob already have to remember so many different passwords that remembering another complex password is too difficult for them. So let us ignore this case. The second solution is to make decryption expensive. In other words every time Eva tries a new password, the program spends a fair amount of time to decrypt and to give the result whether the password matched or not. If one decryption takes 30 seconds, then Eva has to wait a year to try all the passwords from the dictionary. Of course Eva can use a supercomputer with parallel computation to reduce that time, but in any case a lot of computational work has to be done to break the encryption.

Strengthening Password Using Time

The most obvious solution is to increase the complexity of the decryption by extra computational work. For example, the original password can be digested by a hash function in a number of cycles before applying to encryption. However, the problem here is - how much of the 'extra work' is enough? With a fixed number of cycles the number must be known that adds a parameter to the algorithm. If you add too little, then it does not make it too hard for Eva to break the decryption. If you add too much, then the decryption for Bob can be unusable on a weak computational device.

A solution is to let the algorithm increase the decryption complexity by Alice giving a certain amount of time when encrypting. From Alice's point of view - she starts the encryption process and then decides when to stop. The amount of time when she waits defines the complexity of the future decryption: the longer period, the more time-consuming decryption is.

In this case the decryption process must solve a corresponding computational problem. On a similar computational device this would take as much time as Alice waited. For Eva, every attempt to match the password requires the same computational effort, i.e. spent time.

A Cipher Example

Let us consider a cipher presented in the Diagram. To encrypt message M Alice uses a one-way function to generate the
cipher pattern X out of the password P and the salt S. Salt is a random string added to the password to make the cipher pattern different for every encryption. Obviously the salt has to be passed together with the encrypted message, so Bob is able to generate the same cipher pattern. For Eva, however, the salt prevents pre-digestion of the dictionary to speed up cracking the password.

Instead of using the cipher pattern immediately Alice lets the algorithm to digest it again and again in a cycle until Alice presses stop. The algorithm selects the best pattern according to a predefined rule; for example, the smallest or the greatest. This rule ensures that the generation is logarithmic in time -- the number of new best found patterns is O(log n). The found cipher pattern X is used to encrypt the message M producing the ciphertext C. To get C out of M and X any strong cipher algorithm can be used.

The decryption process works in a similar way. However this time every new best found cipher pattern is tried to decrypt the message. This process continues until the message is decrypted. The decryption diagram is the same with the exception that the message M and the cipher text C are swapped.

An alternative to cyclic digestion of cipher pattern can be produced by an enumerated suffix appended to the password, such as 1,2,3,... changing the password to "john1", "john2", etc. If Alice encrypts the message for herself to decrypt later, she may remember a part of the suffix that can make decryption faster. For example, while encrypting, the algorithm has found the combination "salt+john5663058" producing the smallest X and reported to Alice the suffix 5663058. If Alice remembers the first digit 5 and uses "john5" to decrypt, the decryption will take 10 times faster because it has to run only up to 663058 instead of 5663058. The suffix can be constructed of any symbols. The only condition is that it is selected from a reproducible sequence.

A Numerical Example


Wednesday, 27 July 2016

Mathematics and art

Programming blends together mathematics and art: small programs require nothing but formal thinking and big programs require nothing but art.

Wednesday, 29 June 2016

How to value a presentation or a paper

Sometimes you like a presentation or a paper and sometimes you don't. I decided for myself (and it is my personal opinion) the following list of imaginary points of goodness.

A graph of a diagram representing numbers (e.g. pie chart) is (+1).

A magic number: (-1). This is a number appearing from nowhere and not explained.

Two formulae: (+1). One formula is not enough; it is 0. So the total number of points for all formulae is their number divided by 2.

Two undefined abbreviations or two domain specific jargon words: (-1).

A block diagram or an algorithm: (-1).

A picture representing idea (+1). How to distinguish it from a block diagram? If the reader/audience can draw this picture after read or presentation, then it is (+1) otherwise it is as above (-1).

A list of items is tricky. If the reader/audience know why the number of items is that exactly number - not more not less, then it is (+1). If the items appear arbitrary or the list is not surely complete, then it is (-1).

A table is (0), and any text is (0).

Known Unknown and Unknown Known

Things that we do and don't know that we know and don't know have simple names.

Known known I know that I know Facts
Known unknown I know that I don't know Questions
Unknown known I don't know that I know Assumptions
Unknown unknown I don't know that I don't know Reality

Friday, 27 May 2016

Good things

Good and beautiful things are always the result of either a simple algorithm or rigorous elimination of unnecessary.

Sunday, 24 April 2016

Scientific method

Is it possible to prove scientifically that the scientific method is the right method to pursue science?

Friday, 8 April 2016

Principle of supergoodness fragility

The idea that goodness is fragile is known. The principle says: for something to be good every part of it has to be good. If just one part is bad, then the whole thing is bad. Badness is not the opposite: for something to be bad not all parts have to be bad.

This principle can be extended to fragility of supergoodness, which is the quality when all parts are in agreement with each other. While a good thing stops being good when at least one of its parts is changed to bad, a supergood thing stops being good when any of its parts changes, just changes, not necessarily to bad.

A computer, for example, with its parts is a good thing, because if you fry CPU it becomes bad, but if you replace it with a better model, it remains good. A document signed with a digital signature, on the other hand, is a supergood thing, because any change invalidates the signature. A good art or poetry is just good, but a masterpiece is supergood - nothing can be changed to make it better.

Monday, 21 March 2016

Bad news

It is not a surprise we cannot know everything. What is sadder is that we cannot learn anything at all unless we allow our brain to learn it. The fact that we can learn some things is a consequence of our brain being hardwired for survival during aeons of evolution.

Friday, 26 February 2016

What is it like to be?

The problem that we encounter when thinking about whether a living creature has consciousness or not, comes from our predisposition to label whether the creature is sentient. For example, dog owners have no doubt that dogs are sentient and conscious. At the same time many including religious devotees believe that animals do not have “soul”, being mere biological devices. To my opinion the concept of sentience is a fallacy. Umwelt creates such a unique self-awareness experience, that it is impossible to make an abstraction out of it and to translate it into another creature’s mind. We can imagine being another person, being an ape, or even a bat [“What Is it Like to Be a Bat?”]. It is much more difficult to imagine being an ant or a cell in your body because behaviour of simpler organisms follow strict rules to greater extent than ours. They possess less “free will”. But imagining being another living being is not a change of umwelten, it is rather taking your exact umwelt into another body. The next time you wonder what that thing feels looking at the world, you won’t know. It tries, as any other God’s creature, to find its own harmony between what it can do and what the world can do with it.

Intelligent design 2

If human had been created by intelligent design, we would definitely have wheels, and probably a power plug.