Bird
Raised Fist0
PostgreSQLquery~5 mins

Password authentication methods in PostgreSQL - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime

Start learning this pattern below

Jump into concepts and practice - no test required

or
Recommended
Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong
Time Complexity: Password authentication methods
O(n)
Understanding Time Complexity

When a user tries to log in, the system checks their password. We want to understand how the time to check a password changes as more users or data are involved.

How does the system's work grow when verifying passwords?

Scenario Under Consideration

Analyze the time complexity of this password check query.


SELECT * FROM users
WHERE username = 'user123'
AND password_hash = crypt('input_password', password_hash);

This query finds the user by username and checks if the stored password hash matches the input password after hashing.

Identify Repeating Operations

Look for repeated work in the query.

  • Primary operation: Searching the users table for the username.
  • How many times: Once per login attempt, but depends on how many users are in the table.
How Execution Grows With Input

The time to find the username depends on how many users exist.

Input Size (n)Approx. Operations
10About 10 checks if no index
100About 100 checks if no index
1000About 1000 checks if no index

Pattern observation: Without an index, the search grows linearly with the number of users.

Final Time Complexity

Time Complexity: O(n)

This means the time to check a password grows directly with the number of users if no special search method is used.

Common Mistake

[X] Wrong: "Password checks always take the same time no matter how many users exist."

[OK] Correct: Without an index, the database must look through many users, so more users mean more work and longer time.

Interview Connect

Understanding how password checks scale helps you design systems that stay fast as they grow. This skill shows you can think about real-world performance.

Self-Check

"What if we add an index on the username column? How would the time complexity change?"

Practice

(1/5)
1. Which password authentication method in PostgreSQL is considered more secure and recommended for use?
easy
A. scram-sha-256
B. md5
C. password
D. trust

Solution

  1. Step 1: Understand common PostgreSQL password methods

    PostgreSQL supports several password authentication methods including md5 and scram-sha-256.

  2. Step 2: Compare security levels

    SCRAM-SHA-256 is a newer, more secure method than MD5, which is older and less secure.

  3. Final Answer:

    scram-sha-256 -> Option A

  4. Quick Check:

    More secure method = scram-sha-256 [OK]
Hint: SCRAM is newer and stronger than MD5 for passwords [OK]
Common Mistakes:
  • Confusing md5 as more secure than scram-sha-256
  • Choosing 'password' which sends plain text
  • Selecting 'trust' which requires no password
2. Which line correctly sets password authentication to SCRAM in the pg_hba.conf file?
easy
A. host all all 0.0.0.0/0 password
B. host all all 0.0.0.0/0 md5
C. host all all 0.0.0.0/0 scram-sha-256
D. host all all 0.0.0.0/0 trust

Solution

  1. Step 1: Identify the correct authentication method syntax

    The pg_hba.conf file uses lines like 'host all all address method' to set authentication.

  2. Step 2: Match method to SCRAM

    To use SCRAM, the method must be exactly 'scram-sha-256'.

  3. Final Answer:

    host all all 0.0.0.0/0 scram-sha-256 -> Option C

  4. Quick Check:

    SCRAM method line = host all all 0.0.0.0/0 scram-sha-256 [OK]
Hint: SCRAM method is 'scram-sha-256' exactly in pg_hba.conf [OK]
Common Mistakes:
  • Using 'md5' instead of 'scram-sha-256' for SCRAM
  • Confusing 'password' with SCRAM
  • Omitting the IP address or using wrong format
3. Given this pg_hba.conf line: host all all 192.168.1.0/24 md5, what happens when a user connects from IP 192.168.1.15?
medium
A. The user must use SCRAM authentication.
B. The user connects without a password.
C. The connection is rejected automatically.
D. The user must provide a password hashed with MD5 to authenticate.

Solution

  1. Step 1: Analyze the IP range and method

    The line applies to IPs in 192.168.1.0/24, which includes 192.168.1.15, and uses md5 authentication.

  2. Step 2: Understand md5 authentication behavior

    MD5 requires the client to send an MD5-hashed password for authentication.

  3. Final Answer:

    The user must provide a password hashed with MD5 to authenticate. -> Option D

  4. Quick Check:

    IP in range + md5 method = MD5 password required [OK]
Hint: MD5 method means password hashed with MD5 is required [OK]
Common Mistakes:
  • Assuming SCRAM is used instead of MD5
  • Thinking no password is needed
  • Believing connection is rejected without password
4. You set host all all 0.0.0.0/0 scram-sha-256 in pg_hba.conf but users still connect without password prompts. What is the likely cause?
medium
A. The scram-sha-256 method is misspelled
B. PostgreSQL was not reloaded after changing pg_hba.conf
C. Users have no passwords set in the database
D. The IP address range is incorrect

Solution

  1. Step 1: Check if configuration changes are active

    Changes to pg_hba.conf require PostgreSQL reload to take effect.

  2. Step 2: Identify why password prompts are missing

    If users connect without password prompts, likely the new method is not active due to missing reload.

  3. Final Answer:

    PostgreSQL was not reloaded after changing pg_hba.conf -> Option B

  4. Quick Check:

    Config changes need reload = missing reload causes issue [OK]
Hint: Always reload PostgreSQL after pg_hba.conf changes [OK]
Common Mistakes:
  • Assuming misspelling causes no prompt instead of error
  • Ignoring need to reload server
  • Thinking IP range affects password prompt
5. You want to enforce SCRAM authentication only for users connecting from the local network (192.168.0.0/16) and allow password authentication (md5) for others. Which two lines in pg_hba.conf achieve this correctly?
hard
A. host all all 192.168.0.0/16 scram-sha-256 host all all 0.0.0.0/0 md5
B. host all all 0.0.0.0/0 scram-sha-256 host all all 192.168.0.0/16 md5
C. host all all 192.168.0.0/16 md5 host all all 0.0.0.0/0 scram-sha-256
D. host all all 0.0.0.0/0 trust host all all 192.168.0.0/16 scram-sha-256

Solution

  1. Step 1: Understand pg_hba.conf line order and matching

    PostgreSQL checks lines top to bottom and uses the first matching rule.

  2. Step 2: Set SCRAM for local network first, then md5 for others

    Line 1: local network with scram-sha-256; Line 2: all others with md5.

  3. Final Answer:

    host all all 192.168.0.0/16 scram-sha-256 host all all 0.0.0.0/0 md5 -> Option A

  4. Quick Check:

    Specific local network first, then general others [OK]
Hint: Put specific IP range first, general last in pg_hba.conf [OK]
Common Mistakes:
  • Reversing line order causing wrong method to apply
  • Using 'trust' which disables password
  • Assigning md5 to local network instead of SCRAM