2 eggs and a K-floors building puzzle

You have absolutely identical 2 eggs and empty K-story building. You can throw eggs from any floor and see if it was broken or not. If not, you can reuse it again momentarily. You need to identify the lowest floor, starting from which eggs is broken if thrown (“breaking floor”) in minimum possible steps in worst case.

Solution is here: the-problem-of-eggs-and-a-building.pdf

Advertisements

Secret question as the Big Security Issue and some solutions

Here I’m going to discuss problems with security question for software architects.

Problem description

What is the way for hackers to access data of user’s account. It’s easy nowadays to let users use only cryptosecure passwords.  You can use this password meter if you want to tell them that their password is insecure and use the same code on server side to not to let user to set it. So let us assume that user’s password is already secure. But you probably want user to have a chance to reset her/his password if she/he has forgotten it. And here comes most of the issues. In my experience your security question either assume insecure answer or hard to use for users since they could have more than one correct answer for the security question. In any case this answer is far less cryptosecure then regular password, which makes it a security hole if used directly for show/change password. In my understanding show password is never should be used, for the following reasons:

  1. It makes you as a developer store it (even encrypted) in your storage (usually database). This approach is VERY bad since if some hacker will get access to the database she/he will get all password for all users. It is similar issue as storing credit card in your database and could be even worse, since users tend to use the same password everywhere. Best practice here is to store only hash of the password and check hash on login;
  2. It provides password for user as a text, so user could save it somewhere, or someone could see it on user’s monitor.

There are recommendations for users how to use security question in more secure way, but I doubt many follows it. Change the password will not show hacker old password but still it is easy way to get to the system.

One more huge issue is that answer for security question is stored in database as text or slightly encripted text (instead of hash). This opens up the same issue as discussed earlier.

Problem solutions

Ideally, if you can afford yourself not to use security question at all it could be a solution (although, I don’t think it is possible nowadays) . Since even the following solution will be limited by security of user’s email account.

The only you could do here is the following:

  1. Use more than one security question and use them either randomly and/or more than one at the same time;
  2. Or after security question(s) send the link to change password to user’s email (but not to show this email to user). In this case you will depend on security of user’s email. But if you don’t send link by email and just let user to change password this means that you providing access to user’s account secured only by secure questions which are far less cryptosecure. Alternatevely you can just show user’s hint for password, not the password itself.
  3. This change password link should expire and contain some random token to check you don’t allow anyone else to use the same link to change password, and this token should expire immediately after password is changed and surely should be specific to the user (but should not be generated using any user’s information). The link itself must also not contain any information about the user;
  4. Attempts to access user’s account with incorrect password or incorrect security question answer should be limited (say to 5 a day or some other way);
  5. Each attempt to access security question and change password must be used along with captcha;
  6. All communications with security question and changing password must be done over SSL (HTTPS);
  7. Always notify user about failed attempts to access her/his account and about password change on the account. Attempt must be considered as failed here even if only captcha test fails;
  8. Treat answers to security questions as alternative passwords and work with them the same way, i.e. use password input to enter an answer first time and to input it from the user on password reset process. Store only HASH of the answer not the answer itself. This is, possibly, not very convenient for the user, but will help to keep her/his secret is you database is compromised, so I would call it understandable inconvenience.

Pay attention to 5 which is usually forgotten. Captcha here, I would say playing not only it’s primary role, but also makes path to change password this way uncomfortable for user, which make her/him to use password security versus security question access. It is, I would say,  administrative way of making users not to use this way. I would also do a multi-step change password procedure.

Note on password change process

The procedure of password change should be the following:

  1. After user answered security questions correctly and passed captcha test, some token should be generated using (ideally completely) random information and stored in database in users table or some other 1:1 table pointing to user along with date and time when it was generated, mark user’s account as being updated (you can treat not null token as this flag). Link to change account should be generated like this: https://yoursite.com/secure/passupdt?t=<NEWLY_GENERATED_TOKEN&gt;   For example it could be https://yoursite.com/secure/passupdt?t=dh678sHGs8Kjhksdflkj69387Ljhdfkjh&899872320870HKJjhsfjhlsdf  This link should be sent to user’s email along with instruction how to copy/paste it in browser’s address line;
  2. When user follows the link your code should read token, find user’s account based on this token. Make sure token is not expired (you can, for example, check that it was generated not earlier than 24 hours ago).  Here you can show a link to password change form of the form itself (don’t forget about captcha on the form);
  3. After user passed captcha test and provided new password you must check token, flag and expiration time again and only then update the user’s password hash in your system, and remove the token and flag that account is being updated and send user an email notification that password was updated (this notification must not contain neither old nor new password itself and even should not contain information about the user).

There is a possibility that user will try to access her/his account regular way (with regular password) after step 1 or step 2. There two possibilities: if this attempt was successful or not.

  • If it was successful (means that user remind her/his password and successfully login) you must immediately clear token and token flag in login action and notify user that there was an attempt to change account’s password;
  • If it was not successful I don’t see anything you can do for change password process  (except regular login limitations and captcha starting form second failed attempt). Just notify user about one more failed attempt.

There is one more thing here. If user selects to change password link but he always had successful login before – this means that this activity should be considered as suspicious and user should be asked for her/his password before proceeding. If password was correct then user should be logged in and redirected to regular first-after-login page, if password was incorrect then user should be notified (by email/SMS) and only then proceed to security questions. It is clear that hackers more likely will attempt to attack security questions and not password. One other way for you to avoid it could be not to provide access to forget_password link before user try to access account regular way and fail.

Again as an alternative instead of a link with token to change a password you can send temporary password to the user, who will have to change it on first login.

Puzzle with weights

The following is a programming task from my childhood:

Assume, we have a weight of integer value (say, X) and an infinite set of weights 1, 3, 9, 27, … Assuming that we have ideal pharmaceutical scales. The task is to balance weight X using set of weights, if we can put any amount of weights on any scale.

The solution is to factor X in 3-nary presentation:

X = x_0 * 1 + x_1 * 3 + x_2 * 9 + … + x_n * 3^n

where all x_i are in {0, 1, 2} (i.e. in mod3 ring in mathematical terminology).

Let’s use [y] notation for integer part of y.

Let’s assume that we put X on scale A and the second scale has name B. Let’s denote Y sum of all weights on A and Z as sum of all weights on B.

We denote Y = y_0 * 3^0 + y_1 * 3^1 + … + y_n * 3^n

At the beginning we have Y = X and Z = 0;

The idea is to go from 0 to n (and, possibly n+1) and do the following (*):

  • if x_i = 0 we are fine, do nothing;
  • if x_i = 1, put 3^i on scale B;
  • if x_i = 2, put 3^i on scale A and now Y = Y + 3^i, which is, actually makes y_i = 0 and y_(i+1) = y_(i+1) + 1;

Now let’s prove that X will be balanced by this algorithm in not more than [log_3(X)]+1 steps by induction:

[

1) if n = 0, X in {0, 1, 2} by (*) we have

ether 0 on all scales in 1 step

or 1 on both scales in 1 step

or {X, 1} on scale A and 3 on scale B in 2 steps;

2) let’s assume that the proposition is correct for any k <= n, and we have log_3 X = n+1, so, assuming that we’ve already done n steps (added or did not added 1 on level n+1)

we have now 4 possible situations:

a) y_(n+1) in {0, 1} on step n and [step do not add 1 to y_(n+1);

b)  y_(n+1) = 2 on step n and [step do not add 1 to y_(n+1);

c)  y_(n+1) in {0, 1} on step n and [step adds 1 to y_(n+1);

d)  y_(n+1) = 2 on step n and [step adds 1 to y_(n+1);

I) in cases a) – c) on step n+ 1 we have y_(n+1) in {0, 1, 2} and y_k = 0 for all k > (n+1); by (*) and like in 1) we can complete balancing in not more than 2 steps, so having total (n+2) steps at maximum;

II) in case d) on step n+1 we have y_ (n+1) = 0 and y_(n+2) = 1 which can we balanced by putting 3^(n+2) on B, which adds 2 more steps casing finish in (n+2) steps.

We also pay attention, that for each n we put 3^n only on A if y_n = 2 or on B if y_n = 1 and nowhere if y_n = 0. So we do not need more than 1 weight with value 3^n for all n.

]

This proposition arise 1 interesting question: What is the least amount of weights k^n for all n do we need to balance any X on such scales?

First of all, let’s point our attention, that the question is trivial if the only place we can put our weights (except X) is B. In this case we have to have k-1 weights of each k^i weight which represents X in k-nary system.

We have 2 cases k is even and k is odd.

I) If k is odd that in k-nary system x_i will be in {0, … , k-1} where k-1 is even. In this case let’s prove we need (k-1)/2 weights.

For each i if we have y_i <= (k-1)/2, we put y_i weight on B. if y_i >= (k-1)/2  (**) we have z = k – y_i  <= (k-1)/2 (***) is the amount s.t. (y_i + z) mod k = 0 and (y_i + z) div k = 1.

It means that z is the amount we can put on A to have 0 there and shift 1 to the next level.  And we can not have amount of weights < (k-1)/2 since (**) and (***) can reach equality.

II) if k is even, k-1 is odd, let’s denote k-1 = 2l+1,  [(k-1)/2] = l weights is not enough since there is a middle value [(k-1)/2] + 1 = l+1which is strictly greater than [(k-1)/2] = l  and l is not enough to shift it to next level, since (l+1) + l = 2l + 1 = k-1 <k, but [(k-1)/2]+1 = l + 1 weight is enough, since, we can up on B amounts up to l + 1 and z = 2l – (l + 1) = l – 1 < l + 1, so we have enough amount of weights to shift to the next level. By the way, [(k-1)/2] + 1 = l + 1 = (2l + 2)/2 = k/2

To summarize, we have the following:

The least amount of k^i weights for each i to balance scales  is (k-1)/2 is k is odd and k/2 if k is even. Or, simply, [k/2]

In our proposition we had odd situation so we had (3-1)/2 = 1 weight enough to balance.