Is it possible to determine password strength without knowing the password?

I would figure there are two ways they've come up with the information that they drew that conclusion from.

1. They ran the net accounts /domain command on a users computer which dumped the password complexity requirements for your organization (assumes Windows / Active Directory)
2. They successfully brute forced (or guessed) user passwords because they were weak. Recent password dumps like LinkedIn have provided a trove of real-world passwords that pen-testers have been using in the field to try to crack passwords.

Without further information it's hard to say how they've come to that conclusion (we have no idea what the red team did or what was in scope) but those two ways are how I would assume they did it.

Not really.

What a tester may know:

• Password policy: When signing up, or when changing a password, the application may restrict the possible passwords, leading to weak passwords. The password policy may also allow weak passwords, but that would be a separate issue.
• Password length: The tester may have gained information about the password length, for example via blind SQL injection, and may not have bothered to gather the password.
• The password: The tester may have gained access to the passwords, for example via SQL injection or via bruteforcing the login. But these issues should be listed separately as well.

Yes, it is possible.

Windows networks may be vulnerable to Null Session attacks which allow the attacker to enumerate system details:

...gain anonymous access to IPC$. By default, Windows NT family hosts allow anonymous access to system and network information through NetBIOS, so the following can be gleaned:

• User list
• Machine list
• NetBIOS name list
• Share list
• Password policy information
• Group and member list
• Local Security Authority policy information
• Trust information between domains and hosts

An appropriate, complete and professional Pen test report has to include all the findings in details. It should list not only how they came up with their conclusions, but also which methods they have used, and potentially screenshots of their proofs. If not, you can ask for further details and they are obliged to explain or provide the details.

That said, without further details, I believe what they could do is find the password policy in general, and based on it advise to change it or improve it, if they believe it is weak or incomplete. Even then, they cannot and should not assume that a given user password is weak only because of that policy. Complex or strong passwords might still be created (in some cases) even with a not-so-strong password policy.

Most weaknesses occur when the user chooses a weak password, regardless of the password policy in place.

Repeat after me: It is not possible to determine password strength even by knowing the password!

Again: It is not possible to determine password strength even by knowing the password!

On the other hand, you can know the password strengths by looking at your password policy documents. If your password policy document does not specify how passwords should be generated, then they are correct that you have weak password policy and therefore weak password strength.

A good password policy specifies at least the minimum entropy requirement for the various secure sections and the password generation method, instead of how passwords should superficially look like.

There can be some information about how the passwords are stored. e.g., Sharity Light guide, section 3, recommends setting "LmCompatibilityLevel"=dword:1" for greater compatibility. This does cause passwords to be stored in a less secure way.

In this case, what the user types is not the detected problem. However, what is being referred to is how the credential information is getting stored. By changing such storage details, the result could reasonably be described as a change that did "strengthen passwords".