Claims:1. A computer implemented method comprising:
determining minimum length lmin for a password;
dividing number of derivable passwords having the minimum length lmin into a pre-determined number of bins, each of the bins being characterized by a pattern;
allocating to at least one user, a bin from the pre-determined number of bins for password creation such that density of the pre-determined number of bins is substantially uniform; and
verifying that the password created by the at least one user matches the pattern characterizing the assigned bin.

2. The computer implemented method of claim 1, wherein determining minimum length lmin for a password is based on maximum number of users ?, computing power a of bin attackers and a pre-determined success rate Euniform (success) of a bin attacker.

3. The computer implemented method of claim 1, wherein the number of derivable passwords having the minimum length lmin is 95lmin.

4. The computer implemented method of claim 1, wherein the pre-determined number of bins is 4lmin.

5. The computer implemented method of claim 1, wherein allocating to at least one user comprises a technique selected from the group of round robin technique, random technique and power of two choices technique.

6. A system comprising:
one or more processors;
a communication interface device;
one or more internal data storage devices operatively coupled to the one or more processors for storing:
a password length decider configured to determine minimum length lmin for a password;
a password bin generator configured to divide number of derivable passwords having the minimum length lmin into a pre-determined number of bins, each of the bins being characterized by a pattern;
a password bin allocator configured to allocate to at least one user, a bin from the pre-determined number of bins for password creation such that density of the pre-determined number of bins is substantially uniform; and
a password bin verifier configured to verify that the password created by the at least one user matches the pattern characterizing the assigned bin.

7. The system of claim 6, wherein the minimum length lmin for a password is based on maximum number of users ?, computing power a of bin attackers and a pre-determined success rate of a bin attacker.

8. The system of claim 6, wherein the number of derivable passwords having the minimum length lmin is 95lmin.

9. The system of claim 6, whereinthe pre-determined number of bins is 4lmin.

10. The system of claim 6, wherein the password bin verifier is further configured to employ a technique selected from the group of round robin technique, random technique and power of two choices technique.
, Description:
FORM 2

THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003

COMPLETE SPECIFICATION
(See Section 10 and Rule 13)

Title of invention:
SYSTEMS AND METHODS FOR CREATING SECURE PASSWORDS

Applicant:
Tata Consultancy Services Limited
A company Incorporated in India under the Companies Act, 1956
Having address:
Nirmal Building, 9th floor,
Nariman point, Mumbai 400021,
Maharashtra, India

The following specification particularly describes the embodiments and the manner in which it is to be performed.

TECHNICAL FIELD
[0001] The embodiments herein generally relate toinformation security, and more particularly to systems and methods for resisting guessing attacks.

BACKGROUND
[0002] For years passwords have been primary means for authenticating users. Legitimate users’ access rights are compromised when unauthorized users are successful in guessing user identifier/password combination of legitimate users. Guessing user identifier/ password combinations via the internet is commonly referred to as online attacks. Such attacks are generally restricted by lock-out policies implemented on websites. Another form of online attacks is trawling, wherein unauthorized users can attempt guessing on other accounts when some accounts are locked out. Trawling attacks are generally countered by blacklisting popular passwords and their common variants. However, offline attacks, wherein attackers are in possession of the complete password database and therefore can make unlimited attempts to break the password, is a serious threat to password security.
[0003] Human generated passwords are drawn from a small search space which makes them vulnerable to guessing attacks. Websites generally enforce a common composition policy for passwords on all users. Also, minimum password length is fixed for all users in an ad-hoc manner irrespective of the number of registered users, thereby reducing the effort required in guessing attacks. Guessing attacks, therefore continue to pose a severe threat to password security today. Creating secure passwords continues to remain a challenge, particularly with proliferation of internet services that make resources vulnerable to unauthorized users.

SUMMARY
[0004] This summary is provided to introduce concepts related to password protection against guessing attacks wherein attackers have access to encrypted password files. This summary is neither intended to identify essential features of the claimed subject matter nor is it intended for use in determining or limiting the scope of the present disclosure.
[0005] Systemsand methods of the present disclosure enable creating secure passwords based on utilizing password search space to the maximum extent possible. Systems and methods of the present disclosure also enable determining of minimum length for a password that can counter guessing attacks.
[0006] In an aspect, there is provided a computer implementedmethodfor creating secure passwords, the method comprising: determining minimum length lminfor a password; dividing number of derivable passwords having the minimum length lmin into a pre-determined number of bins, each of the bins being characterized by a pattern; allocating to at least one user, a bin from the pre-determined number of bins for password creation such that density of the pre-determined number of bins is substantially uniform; and verifying that the password created by the at least one user matches the pattern characterizing the assigned bin.
[0007] In another aspect, there is provided a system for creating secure passwords, the system comprisingone or more processors;a communication interface device;one or more internal data storage devices operatively coupled to the one or more processors for storing: a password length decider configured to determine minimum length lmin for a password; a password bin generator configured to divide number of derivable passwords having the minimum length lmin into a pre-determined number of bins, each of the bins being characterized by a pattern; a password bin allocator configured to allocate to at least one user, a bin from the pre-determined number of bins for password creation such that density of the pre-determined number of bins is substantially uniform; and a password bin verifier configured to verify that the password created by the at least one user matches the pattern characterizing the assigned bin.
[0008] In yet another aspect, there is provided a computer program product comprising a non-transitory computer readable medium having a computer readable program embodied therein, wherein the computer readable program, when executed on a computing device, causes the computing device to: determine minimum length lmin for a password; divide number of derivable passwords having the minimum length lmin into a pre-determined number of bins, each of the bins being characterized by a pattern; allocate to at least one user, a bin from the pre-determined number of bins for password creation such that passwords are distributed substantially uniformly across the pre-determined number of bins; and verify that the password created by the at least one user matches the pattern characterizing the assigned bin.
[0009] In an embodiment, determining minimum length lmin for a password is based on maximum number of users ?, computing power a of bin attackers and a pre-determined success rate of a bin attacker.
[0010] In an embodiment, wherein the number of derivable passwords having the minimum length lmin is 95lmin.
[0011] In an embodiment, the pre-determined number of bins is 4lmin.
[0012] In an embodiment, allocating to at least one user comprises a technique selected from the group of round robin technique, random technique and power of two choices technique.

BRIEF DESCRIPTION OF THE DRAWINGS
[0013] The embodiments herein will be better understood from the following detailed description with reference to the drawings, in which:
[0014] FIG. 1illustrates a utilized password search space as known in the art;
[0015] FIG. 2A illustrates a utilized password search space in accordance with an embodiment of the present disclosure;
[0016] FIG. 2Billustrates a password search space and its division into bins in accordance with an embodiment of the present disclosure;
[0017] FIG. 3 illustrates a graphical representation of success rate of a bin attacker who learns bin density from a breached database;
[0018] FIG. 4 illustrates an exemplary block diagram of a system for preventing guessing attacks in accordance with an embodiment of the present disclosure;
[0019] FIG. 5A and 5B illustrate exemplary flow diagrams of a computer implemented method for preventing guessing attacksusing the system of FIG. 4 in accordance with an embodiment of the present disclosure;
[0020] FIG. 6 illustrates a graphical representation of minimum length lmin for a password versus number of users ? for desired Euniform(success)=0, in accordance with an embodiment of the present disclosure; and
[0021] FIG. 7A and FIG. 7B illustrate password bin allocation and creation of a new password in the assigned bin respectively, in accordance with an embodiment of the present disclosure.
[0022] It should be appreciated by those skilled in the art that any block diagram herein represent conceptual views of illustrative systems embodying the principles of the present subject matter. Similarly, it will be appreciated that any flow charts, flow diagrams, state transition diagrams, pseudo code, and the like represent various processes which may be substantially represented in computer readable medium and so executed by a computing device or processor, whether or not such computing device or processor is explicitly shown.

DETAILED DESCRIPTION
[0023] The embodiments herein and the various features and advantageous details thereof are explained more fully with reference to the non-limiting embodiments that are illustrated in the accompanying drawings and detailed in the following description. The examples used herein are intended merely to facilitate an understanding of ways in which the embodiments herein may be practiced and to further enable those of skill in the art to practice the embodiments herein. Accordingly, the examples should not be construed as limiting the scope of the embodiments herein.
[0024] The words "comprising," "having," "containing," and "including," and other forms thereof, are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items.
[0025] It must also be noted that as used herein and in the appended claims, the singular forms "a," "an," and "the" include plural references unless the context clearly dictates otherwise. Although any systems and methods similar or equivalent to those described herein can be used in the practice or testing of embodiments of the present disclosure, the preferred, systems and methods are now described.
[0026] Some embodiments of this disclosure, illustrating all its features, will now be discussed in detail. The disclosed embodiments are merely exemplary of the disclosure, which may be embodied in various forms.
[0027] Before setting forth the detailed explanation, it is noted that all of the discussion below, regardless of the particular implementation being described, is exemplary in nature, rather than limiting.
[0028] Referring now to the drawings, and more particularly to FIGS. 1 through 6B, where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments and these embodiments are described in the context of the following exemplary system and method.
[0029] The expression “user” in the context of the present disclosure refers to a user registered with a computer system or website to access software.
[0030] The expression “password” in the context of the present disclosure refers to a secret string of characters for authenticating access to a service hosted on a remote computer system via the internet.
[0031] The expression “guessing attacks” as referred to in the present disclosure refers to both online and offline attacks wherein attackers attempt to guess user identifier/password combinations.
[0032] The expression “partition” refers to non-overlapping sub-search spaces identified within the password search space defined herein above.
[0033] The expression “partition density” or “density” refers to the number of passwords in a password database that belong to a partition divided by the size of partition.
[0034] The expression “partition probability” or “probability refers to the number of passwords in a password database that belong to a partition divided by total number of passwords in the password database.
[0035] The expression “partition attacker” refers to an attacker who learns the partition level features (such as partition densities and probabilities) and assumes every password within a given partition to be equally likely.
[0036] The expression “bin” or “password bin” as referred to in the present disclosure refers to representation of a password in terms of at least 1 alphabet from available 4 alphabets, namely, L, U, D and S, wherein L represents the set of 26 lowercase letters[a-z], U represents the set of 26 uppercase letters [A-Z], D represents the set of 10 digits [0-9] and S represents the set of 33 special characters [!@#$%^&()….].For instance, a password “princess” composed of 8 lowercase letters is represented by L8 bin while a password “monkey12” composed of 6 lowercase letters followed by 2 digits is represented by L6D2 bin. The bin is an instance of the partition as described herein above.
[0037] The expression “bin attacker” refers to an instance of the partition attackerwhich divides the password search space into bins.
[0038] The expression “minimum length lmin” for a password refers to the minimum length for a password as determined, in accordance with the present disclosure, to counter bin attackers.
[0039] The expression “password search space” refers to the number of lmin length passwords that can be derived using 95 characters (26 lowercase, 26 uppercase, 10 digits and 33 special characters) i.e. 95lmin.
[0040] In the context of the present disclosure, expressions “guessing attackers”, “bin attackers” and “partition attackers” may be used interchangeably.
[0041] The expression “computing power” refers to the guessing capability of the bin attacker.
[0042] The expression “capacity” refers to number of passwords represented by the bin. For instance, the capacityof the bin L8, composed of 8 lowercase letters is |L|8 = 268.
[0043] FIG. 1 illustrates a utilized password search space 100 (hypothetical). Although size of the password search space is huge (95lmin), the utilized search space is very small which drastically reduces the effort of partitionattackers. Partition attackers use information from previous password breaches, surveys, attacks and other sources to divide the password search space into partitions. More information the attackers possess, more granular the partitions are. Referring to FIG. 1, wherein the password search space 100 that is very similar to real word password search space is illustrated, it can be assumed that a partition attacker uses information from previous breaches to divide thepassword search space 100 into 16 partitions (4lmin = 42= 16 assuming lmin= 2). It can be seen that 10 partitionsof the search space are not used. All passwords (26 in the illustration) are confined toremaining 6 partitions. Less dense partitions 110 and more dense partitions 112 are illustrative utilized partitions. The password search space is huge (16 partitions) but the utilized search space is small (6 partitions) which clearly shows a gap between available password search space and utilized password search space. The partition attacker can skip the search of unused partitions and utilize available computing resource to explore only the utilized partitions. As the utilized search space is small the partition attacker requires relatively small computing power a to break large number of protected passwords that are confined to few partitions.
[0044] The present disclosure provides proof that success rate of attackers is maximum if partitions are explored in the decreasing order of density. Suppose the partition attacker uses information from previous breaches and other sources to divide a password search space s into n partitions {s1, s2, ……sn}. Let ?>> n represent number of passwords in the breached repository and let ?i denote the count of passwords in partition si. Since the same password can be used by many users, ?i represents multiple count of such repeated passwords. Assume that partition densities are non-uniform. Further without loss of generality, assume that
.
Assume that the partition attacker can generate a guesses for exploring the partitions. If the computation resource a available for the attack is limited, i.e. a < |s|, then the maximum expected success of the partition attacker is,

Where partition i0 is such that
Assume that the attacker distributes the resource a across n partitions {s1, s2, ……sn} as {a1, a2,…an}, i.e., attacker spends effort ai on the partition si.
?(1)
The expected success (number of passwords broken) of the partition attacker is,
?(2)
Therefore,

The present disclosure now provides that the attacker cannot do better than this. Suppose the same effort ais distributed across n partitions of s in some other way, i.e. .
From equation (2) above, the expected success of another partition attacker,

Now,
?(3)
Using equation (1) above, for i? i0.
Also, we know that , for i? i0.
?(4)
Again, using equation (1) above, , for i? i0+2 and
it is seen that , for i? i0+2.

?(5)
Using equations (3), (4) and (5), the following inequality is obtained,

Hence the distribution of effort a given by the equation (1) above is optimal, i.e. the benefit is maximum if partitions are explored greedily in the decreasing order of density.
[0045] FIG. 2A illustrates a utilized password search space 200 in accordance with an embodiment of the present disclosure, wherein the 26 passwords are distributed to ensure that the partitions 210 (16 partitions illustrated) available in the password search space 200 are substantially equally dense. The attacker thus has to explore every partition to break all the passwords.The effort of the partition attacker due to uniform partition density is increased tremendously. The present disclosure proves this as follows –
Theorem:
Suppose that the attacker with limited computing power a explores the first j dense partitions completely and a fraction "f" of the j+1 partition.
Let 0 ? f ? 1 and
then for 1? j ? n,

Proof:


since

Corollary 1: 1? j ? n-1

The proof follows for f = 0 in the above theorem.
Corollary 2: 1? j ? n

The proof follows from Corollary 1.
The expected success of the partition attacker with limited computational power a < |s| is minimum if the partition densities are uniform, i.e. .
Proof: If the partition densities are uniform, then the expected success of the attacker with computations power a < |s| is,

Now, consider the case of non-uniform partition densities. Without loss of generality assume that,

The maximum success for the attacker with computational power a < |s| is,

Where i0 is such that
.
Let
Note that 0 ? f ? 1.

Using the above theorem,

since ,

From corollary 2,


[0046] FIG. 2B illustrates the password search space 200 and its division into bins in accordance with an embodiment of the present disclosure, wherein
L = lower case letter in English {a,….z}, |L| = 26,
U = upper case letters in English {A,…Z}, |U| = 26,
D = digits {0,….9}, |D| = 10, and
S = special character, |S| = 33.
For minimum length lmin of password, when lmin= 2, there are 4lmin= 42= 16 bins as illustrated in FIG. 2B. Each bin represents a class of passwords. For instance LL represents passwords composed of 2 lowercase letters while bin LD represents passwords composed of a lower case letter followed by a digit. Capacity of bin LD as illustrated = 26 x 10 = 260 unique words.
[0047] FIG. 3 illustrates a graphical representation of success rate of a bin attacker who learns bin density from a breached database, Rock you in the instant exemplary representation. The bin attacker uses the learned bin densities to break passwords in other eight breached password databases. As illustrated, the bin attacker can break more than 60% passwords (in most databases) with a = 240 guesses and more than 80% passwords (in most databases) with a = 250 guesses. It may be understood by persons skilled in the art that computing powera = 250 is quite feasible with current computing power.
[0048] It is generally seen that in theabsence of composition policies, passwords are composed using lowercase letters and digits which benefits the bin attacker. To thwart these attacks, websites force users to choose their passwords from a larger password search space, so that the offline attack becomes infeasible. Most websites typically enforce a password composition policy that requires minimum 8 length in addition to the use of at least one lowercase (a-z), uppercase (A-Z), digit (0-9) and special character (!,@,#, etc.) for creating passwords. Since there are 26 lowercase letters, 26 uppercase letters, 10 digits and 33 special characters, the password search space for the offline attacker is at least 958. However, enforcing the same composition policy on all users might cause few bins like U1L6S1D1 (password starting with 1 uppercase followed by 6 lowercase then 1 symbol and 1 digit) or U1L6S1D2(password starting with 1 uppercase followed by 6 lowercase then 1 symbol and 2 digits) to become more popular. The guessing attacker can again target only the utilized dense bins and again break large number of passwords. Thus, enforcing the same composition policies on all users does not counter the bin attacker.
[0049] The table herein below is indicative of potential denser bins used in password creation that are identified when different alphabet sets are enforced upon users. The data (in percentage %) indicates the popularity of denser bins for the given alphabet set.?+ denotes at least one occurrence of lowercase letter, ?* denotes zero or more occurrence of lowercase letter while ?[0,1] at most one occurrence of the alphabet ?? {L, U, D, S} and – indicates the absence of alphabet set in the given website.

[0050] Further, websites do not provide a rationale behind the minimum 8 length requirement of the passwords. This restriction does not take into account the tremendous computing power of the guessing attacker. Websites comprising billion of registered users have the same length requirement (8) as that of websites containing thousands of users, which is not logical. For instance, suppose that a website has 10,000 registered users and minimum password length is 8. Assuming that all 48bins are equally dense, the attacker needs 958/104 guesses on an average to crack a single password. Now consider a setting with a billion registered users and same minimum password length of 8. In this case the attacker requires just 958/109 guesses which is 105 times lesser than 958/104. Thus, in order to counter the bin attacker, the minimum length of the password should depend upon the number of registered users on the website. Specifically for large scale websites that comprise nearly millions or billions of registered users, the required password length should be longer.
[0051] Taking these aspects into account, methods and systems of the present disclosure firstly facilitate creating secure passwords by firstly determining the minimum length lminof passwords that is necessary to counter bin attackers. Secondly, the available password search space is divided into bins and the passwords are distributed such that the bins are substantially equally dense.
[0052] FIG. 4illustrates an exemplary block diagram of a system 400 forpreventing guessing attacks in accordance with an embodiment of the present disclosure and FIG. 5A and FIG. 5B illustrate exemplary flow diagramsof a computer implemented method 500 for preventing guessing attacks using the system of FIG. 4 in accordance with an embodiment of the present disclosure.In an embodiment, the system 400 includesone or more processors(not shown), communication interface or input/output (I/O) interface (not shown), and memory or one or more internal data storage devices (not shown) operatively coupled to the one or more processors. The one or more processorscan be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the processor(s) is configured to fetch and execute computer-readable instructions stored in the memory.In an embodiment, the system 400 can be implemented on a server or in a variety of computing systems, such as a laptop computer, a desktop computer, a notebook, a workstation, a mainframe computer, a server, a network server, cloud, hand-held device and the like.
[0053] The I/O interface can include a variety of software and hardware interfaces, for example, a web interface, a graphical user interface, and the like and can facilitate multiple communications within a wide variety of networks and protocol types, including wired networks, for example, LAN, cable, etc., and wireless networks, such as WLAN, cellular, or satellite. In an embodiment, the I/O interface can include one or more ports for connecting a number of devices to one another or to another server.
[0054] The memory may include any computer-readable medium known in the art including, for example, volatile memory, such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. In an embodiment, the various modules of the system 400 can be stored in the memory.
[0055] The steps of the method 500 of the present disclosure will now be explained with reference to the components of the system 400 as depicted in FIG. 4. At step 502, a password length decider410 determines minimum length lmin for a password.
[0056] As seen from the description above, success rate of the partition attacker is minimum if all partitions are equally dense.

where ? refers to the number of users, |s| refers to the size of the password search space and a refers to the computing power or the number of guesses generated by the partition attacker.
It can be noted that if the number of users ? in the system increases, then the attacker’s success rate also increases. Therefore, just spreading users across different bins is not enough. The system should also ensure that the expected success Euniform (success) of the attacker is bounded. This can be achieved by increasing the search space size |s|.

The size of the password search space s depends upon the length l of the password as well as character set ? used for creating the password.
Therefore,

Using this relation, minimum length lmin for a password can be computed in accordance with the present disclosure to counter the partition attacker as follows –

[0057] Thus in an embodiment of the present disclosure, minimum length lmin for a password is based on maximum number of users ?, computing power a of bin attackers and a pre-determined success rate of a bin attacker. For instance, to protect a website with users ? = 104 from bin attacker (Euniform (success) = 0) with computing power a = 240 and using character set ? = 95, minimum length lmin for a password is approximately 8. While for large scale websites, where the number of users ? = 109, the minimum length lmin for a password to counter a bin attacker with computing power a = 240is nearly 11. FIG. 6 illustrates a graphical representation of minimum length lmin for a password versus number of users ? for desired Euniform (success)=0 and ?=95, in accordance with an embodiment of the present disclosure.
[0058] At step 504, a password bin generator 412 divides number of derivable passwords having length lmin into a pre-determined number of bins, each of the bins being characterized by a pattern. In an embodiment, the number of derivable passwords having password length lmin is 95lmin. In an embodiment, the pre-determined number of bins is 4lmin.Thus at step 504, the password bin generator 412 partitions the password search space of size 95lmin into 4lmin bins having lmin length strings derived using the set s = {L,U,D,S}. For instance, L8, U1L6D1, and the like are all 8 length bins. Every bin represents a class of passwords, e.g. the bin L8 represents 8 length passwords composed entirely of lowercase letters while the bin U1L6D1 represents 8 length passwords that begin with an uppercase letter followed by 6 lowercase letters and a digit. Every bin depending upon its composition has a certain capacity C associated with it. The capacity Ci refers to the number of password strings represented by the ith bin. For instance, the capacity of bin L8 is |L|8 = 268 while the capacity of bin U1L6D1 is |U|1*|L|6*|D|1 = (267)*(101).

[0059] At step 506, thepassword bin allocator 414 allocates to at least one user, a bin from the pre-determined number of bins for password creation such that passwords are distributed substantially uniformly across the pre-determined number of bins.Since a user can create a password that aligns with the pattern characterizing the assigned bin, there is some control over password creation, for the user, without significantly compromising the security.FIG. 7A and FIG. 7B illustrate password bin allocation and creation of a new password in the assigned bin respectively, in accordance with an embodiment of the present disclosure.
[0060] The various allocation techniques that can be employed by the password bin allocator 414 are as given below.
Round Robin: In this technique, the password bin allocator 414assigns a bin to a new user in a round-robin fashion. For this purpose, the system400 reads a file F(a static file comprising 4lmin bins, instead of creating bins in run-time) into a sequential array of bins along with a pointer b to the next available bin. The next available bin is allocated to every new user and the pointer's value is increased to (b+1)%4lmin. In this strategy, keeping a track of number of users in each bin is not necessary. The space required for maintaining the data-structure is proportional to the total number of bins 4lmin, while the computing time required for allocating a bin to the new user is just O(1). The system ensures that the density of every bin is same F/|s|, where F is number of users in the system and |s|=95lmin is the size of search space. In case of database compromise, the attacker can learn the exact number of users in any given bin by finding the current value of b.
Random: In this technique, the password bin allocator 414 randomly generates a bin for the new user. The probability of assigning the bin should be proportional to its size. Otherwise the bins of different capacities will have same number of passwords, disturbing the density uniformity. Therefore, the expected density of a bin is f/s. Since the bins are assigned randomly some bins can get F/s * x - F/s (where x = 1) more users than the expected, wherein the quantity xrefers to a stretch (mathematical). For the random allocatingtechnique, the stretch x is not more than log(4lmin)/log log(4lmin) with high probability. Since log(4lmin)= 2*lmin, x = 2*lmin/log(2*lmin). In this technique, there is no need to keep track of number of users in each bins. Also no pointers are required. The bins are chosen randomly from the File Fand required time is just O(1).One can also generate the lmin length bin randomly without storing them in a file F (generate alphabet ? ? {L,U,D,S}with probability |?|/95) so that the resulting bin densities are uniform and the required space is just O(1).Further, the database breach does not reveal the information about number of passwords in any bin. In an embodiment of the present disclosure, the random allocating technique is a preferred technique for allocating bin to a user.
Power of two choices: In this technique, the password bin allocator 414 randomly chooses two bins and assigns the leastdense bin to the new user. Again the probability of choosing any bin is required to be proportional to its size. Otherwise the bins of different capacities will have same number of passwords, disturbing the density uniformity. Such implementation would require memory to remember the number of users in every bin. So O(4lmin) space is required. The expected density of a bin is F /s. However, the stretch in this strategy depends upon the size of a bin. In case of smaller bins the stretch is 2 * log log(4lmin) = 2 * log(2 * lmin) and for the larger bins the stretch is 4 + e with high probability. In case of database compromise, the attacker can learn the exact number of users in any given bin.
A comparison of different allocation strategies for achieving uniform bin density is provided herein below.
Strategy Space Time Expected density Stretch x
Round Robin O (4lmin) O (1) 1
Random O (1) O (1)
Power of two choices O (4lmin) O (1)

[0061] At step 508, a password bin verifier 416 verifies that the password created by the at least one user matches the pattern characterizing the assigned bin. The system 400 cannot accept the user’s password until it is aligned with the pattern of the assigned bin.
[0062] In accordance with the present disclosure, the password length decider 410 and the password bin generator 412 are required to be invoked only once for a given website whereas the password bin allocator 414 and the password bin verifier416 are invoked every time a new user registers or an already registered user changes his/her password.
[0063] In an embodiment, the password length decider 410, the password bin generator 412, the password bin allocator 414 and the password bin verifier 416 are co-located on a single system, for instance a server system. In another embodiment, the password length decider 410, the password bin generator 412 and the password bin allocator 414 are implemented on a server system and the password bin verifier 416 is implemented both on a client system and the server system. In such an embodiment, the password bin verifier 416 can reject a password at the client system if the password does not satisfy the pattern requirement of the assigned bin.System 400 of the present disclosure can be easily implemented into existing text-based password systems.
[0064] The written description describes the subject matter herein to enable any person skilled in the art to make and use the embodiments of the invention. The scope of the subject matter embodiments defined here may include other modifications that occur to those skilled in the art. Such other modifications are intended to be within the scope if they have similar elements that do not differ from the literal language of the claims or if they include equivalent elements with insubstantial differences from the literal language.
[0065] It is, however to be understood that the scope of the protection is extended to such a program and in addition to a computer-readable means having a message therein; such computer-readable storage means contain program-code means for implementation of one or more steps of the method, when the program runs on a server or mobile device or any suitable programmable device. The hardware device can be any kind of device which can be programmed including e.g. any kind of computer like a server or a personal computer, or the like, or any combination thereof. The device may also include means which could be e.g. hardware means like e.g. an application-specific integrated circuit (ASIC), a field-programmable gate array(FPGA), or a combination of hardware and software means, e.g. an ASIC and an FPGA, or at least one microprocessor and at least one memory with software modules located therein. Thus, the means can include both hardware means and software means. The method embodiments described herein could be implemented in hardware and software. The device may also include software means. Alternatively, the invention may be implemented on different hardware devices, e.g. using a plurality of CPUs.
[0066] The embodiments herein can comprise hardware and software elements. The embodiments that are implemented in software include but are not limited to, firmware, resident software, microcode, etc. The functions performed by various modules comprising the system of the present disclosure and described herein may be implemented in other modules or combinations of other modules. For the purposes of this description, a computer-usable or computer readable medium can be any apparatus that can comprise, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device. The various modules described herein may be implemented as either software and/or hardware modules and may be stored in any type of non-transitory computer readable medium or other storage device. Some non-limiting examples of non-transitory computer-readable media include CDs, DVDs, BLU-RAY, flash memory, and hard disk drives.
[0067] A data processing system suitable for storing and/or executing program code will include at least one processor coupled directly or indirectly to memory elements through a system bus. The memory elements can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code in order to reduce the number of times code must be retrieved from bulk storage during execution.
[0068] Further, although process steps, method steps, techniques or the like may be described in a sequential order, such processes, methods and techniques may be configured to work in alternate orders. In other words, any sequence or order of steps that may be described does not necessarily indicate a requirement that the steps be performed in that order. The steps of processes described herein may be performed in any order practical. Further, some steps may be performed simultaneously.
[0069] The preceding description has been presented with reference to various embodiments. Persons having ordinary skill in the art and technology to which this application pertains will appreciate that alterations and changes in the described structures and methods of operation can be practiced without meaningfully departing from the principle, spirit and scope.