/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */


package org.apache.catalina.authenticator;


import java.io.IOException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.security.Principal;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.StringTokenizer;

import javax.servlet.http.HttpServletResponse;


import org.apache.catalina.LifecycleException;
import org.apache.catalina.Realm;
import org.apache.catalina.connector.Request;
import org.apache.catalina.connector.Response;
import org.apache.catalina.deploy.LoginConfig;
import org.apache.catalina.util.MD5Encoder;
import org.apache.juli.logging.Log;
import org.apache.juli.logging.LogFactory;



/**
 * An <b>Authenticator</b> and <b>Valve</b> implementation of HTTP DIGEST
 * Authentication (see RFC 2069).
 *
 * @author Craig R. McClanahan
 * @author Remy Maucherat
 * @version $Id: DigestAuthenticator.java 1158180 2011-08-16 10:11:43Z markt $
 */

public class DigestAuthenticator extends AuthenticatorBase {

    private static Log log = LogFactory.getLog(DigestAuthenticator.class);


    // -------------------------------------------------------------- Constants

    /**
     * The MD5 helper object for this class.
     */
    protected static final MD5Encoder md5Encoder = new MD5Encoder();


    /**
     * Descriptive information about this implementation.
     */
    protected static final String info =
        "org.apache.catalina.authenticator.DigestAuthenticator/1.0";


    /**
     * Tomcat's DIGEST implementation only supports auth quality of protection.
     */
    protected static final String QOP = "auth";

    // ----------------------------------------------------------- Constructors


    public DigestAuthenticator() {
        super();
        try {
            if (md5Helper == null)
                md5Helper = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
            throw new IllegalStateException();
        }
    }


    // ----------------------------------------------------- Instance Variables


    /**
     * MD5 message digest provider.
     */
    protected static MessageDigest md5Helper;


    /**
     * List of client nonce values currently being tracked
     */
    protected Map<String,NonceInfo> cnonces;


    /**
     * Maximum number of client nonces to keep in the cache. If not specified,
     * the default value of 1000 is used.
     */
    protected int cnonceCacheSize = 1000;


    /**
     * Private key.
     */
    protected String key = null;


    /**
     * How long server nonces are valid for in milliseconds. Defaults to 5
     * minutes.
     */
    protected long nonceValidity = 5 * 60 * 1000;


    /**
     * Opaque string.
     */
    protected String opaque;


    /**
     * Should the URI be validated as required by RFC2617? Can be disabled in
     * reverse proxies where the proxy has modified the URI.
     */
    protected boolean validateUri = true;

    // ------------------------------------------------------------- Properties

    /**
     * Return descriptive information about this Valve implementation.
     */
    @Override
    public String getInfo() {

        return (info);

    }


    public int getCnonceCacheSize() {
        return cnonceCacheSize;
    }


    public void setCnonceCacheSize(int cnonceCacheSize) {
        this.cnonceCacheSize = cnonceCacheSize;
    }


    public String getKey() {
        return key;
    }


    public void setKey(String key) {
        this.key = key;
    }


    public long getNonceValidity() {
        return nonceValidity;
    }


    public void setNonceValidity(long nonceValidity) {
        this.nonceValidity = nonceValidity;
    }


    public String getOpaque() {
        return opaque;
    }


    public void setOpaque(String opaque) {
        this.opaque = opaque;
    }


    public boolean isValidateUri() {
        return validateUri;
    }


    public void setValidateUri(boolean validateUri) {
        this.validateUri = validateUri;
    }


    // --------------------------------------------------------- Public Methods

    /**
     * Authenticate the user making this request, based on the specified
     * login configuration.  Return <code>true</code> if any specified
     * constraint has been satisfied, or <code>false</code> if we have
     * created a response challenge already.
     *
     * @param request Request we are processing
     * @param response Response we are creating
     * @param config    Login configuration describing how authentication
     *              should be performed
     *
     * @exception IOException if an input/output error occurs
     */
    @Override
    public boolean authenticate(Request request,
                                Response response,
                                LoginConfig config)
        throws IOException {

        // Have we already authenticated someone?
        Principal principal = request.getUserPrincipal();
        //String ssoId = (String) request.getNote(Constants.REQ_SSOID_NOTE);
        if (principal != null) {
            if (log.isDebugEnabled())
                log.debug("Already authenticated '" + principal.getName() + "'");
            // Associate the session with any existing SSO session in order
            // to get coordinated session invalidation at logout
            String ssoId = (String) request.getNote(Constants.REQ_SSOID_NOTE);
            if (ssoId != null)
                associate(ssoId, request.getSessionInternal(true));
            return (true);
        }

        // NOTE: We don't try to reauthenticate using any existing SSO session,
        // because that will only work if the original authentication was
        // BASIC or FORM, which are less secure than the DIGEST auth-type
        // specified for this webapp
        //
        // Uncomment below to allow previous FORM or BASIC authentications
        // to authenticate users for this webapp
        // TODO make this a configurable attribute (in SingleSignOn??)
        /*
        // Is there an SSO session against which we can try to reauthenticate?
        if (ssoId != null) {
            if (log.isDebugEnabled())
                log.debug("SSO Id " + ssoId + " set; attempting " +
                          "reauthentication");
            // Try to reauthenticate using data cached by SSO.  If this fails,
            // either the original SSO logon was of DIGEST or SSL (which
            // we can't reauthenticate ourselves because there is no
            // cached username and password), or the realm denied
            // the user's reauthentication for some reason.
            // In either case we have to prompt the user for a logon
            if (reauthenticateFromSSO(ssoId, request))
                return true;
        }
        */

        // Validate any credentials already included with this request
        String authorization = request.getHeader("authorization");
        DigestInfo digestInfo = new DigestInfo(getOpaque(), getNonceValidity(),
                getKey(), cnonces, isValidateUri());
        if (authorization != null) {
            if (digestInfo.validate(request, authorization, config)) {
                principal = digestInfo.authenticate(context.getRealm());
            }
            
            if (principal != null) {
                String username = parseUsername(authorization);
                register(request, response, principal,
                         Constants.DIGEST_METHOD,
                         username, null);
                return (true);
            }
        }

        // Send an "unauthorized" response and an appropriate challenge

        // Next, generate a nonce token (that is a token which is supposed
        // to be unique).
        String nonce = generateNonce(request);

        setAuthenticateHeader(request, response, config, nonce,
                digestInfo.isNonceStale());
        response.sendError(HttpServletResponse.SC_UNAUTHORIZED);
        //      hres.flushBuffer();
        return (false);

    }


    // ------------------------------------------------------ Protected Methods


    /**
     * Parse the username from the specified authorization string.  If none
     * can be identified, return <code>null</code>
     *
     * @param authorization Authorization string to be parsed
     */
    protected String parseUsername(String authorization) {

        // Validate the authorization credentials format
        if (authorization == null)
            return (null);
        if (!authorization.startsWith("Digest "))
            return (null);
        authorization = authorization.substring(7).trim();

        StringTokenizer commaTokenizer =
            new StringTokenizer(authorization, ",");

        while (commaTokenizer.hasMoreTokens()) {
            String currentToken = commaTokenizer.nextToken();
            int equalSign = currentToken.indexOf('=');
            if (equalSign < 0)
                return null;
            String currentTokenName =
                currentToken.substring(0, equalSign).trim();
            String currentTokenValue =
                currentToken.substring(equalSign + 1).trim();
            if ("username".equals(currentTokenName))
                return (removeQuotes(currentTokenValue));
        }

        return (null);

    }


    /**
     * Removes the quotes on a string. RFC2617 states quotes are optional for
     * all parameters except realm.
     */
    protected static String removeQuotes(String quotedString,
                                         boolean quotesRequired) {
        //support both quoted and non-quoted
        if (quotedString.length() > 0 && quotedString.charAt(0) != '"' &&
                !quotesRequired) {
            return quotedString;
        } else if (quotedString.length() > 2) {
            return quotedString.substring(1, quotedString.length() - 1);
        } else {
            return new String();
        }
    }

    /**
     * Removes the quotes on a string.
     */
    protected static String removeQuotes(String quotedString) {
        return removeQuotes(quotedString, false);
    }

    /**
     * Generate a unique token. The token is generated according to the
     * following pattern. NOnceToken = Base64 ( MD5 ( client-IP ":"
     * time-stamp ":" private-key ) ).
     *
     * @param request HTTP Servlet request
     */
    protected String generateNonce(Request request) {

        long currentTime = System.currentTimeMillis();

        
        String ipTimeKey =
            request.getRemoteAddr() + ":" + currentTime + ":" + getKey();

        byte[] buffer;
        synchronized (md5Helper) {
            buffer = md5Helper.digest(ipTimeKey.getBytes());
        }

        return currentTime + ":" + md5Encoder.encode(buffer);
    }


    /**
     * Generates the WWW-Authenticate header.
     * <p>
     * The header MUST follow this template :
     * <pre>
     *      WWW-Authenticate    = "WWW-Authenticate" ":" "Digest"
     *                            digest-challenge
     *
     *      digest-challenge    = 1#( realm | [ domain ] | nonce |
     *                  [ digest-opaque ] |[ stale ] | [ algorithm ] )
     *
     *      realm               = "realm" "=" realm-value
     *      realm-value         = quoted-string
     *      domain              = "domain" "=" <"> 1#URI <">
     *      nonce               = "nonce" "=" nonce-value
     *      nonce-value         = quoted-string
     *      opaque              = "opaque" "=" quoted-string
     *      stale               = "stale" "=" ( "true" | "false" )
     *      algorithm           = "algorithm" "=" ( "MD5" | token )
     * </pre>
     *
     * @param request HTTP Servlet request
     * @param response HTTP Servlet response
     * @param config    Login configuration describing how authentication
     *              should be performed
     * @param nonce nonce token
     */
    protected void setAuthenticateHeader(Request request,
                                         Response response,
                                         LoginConfig config,
                                         String nonce,
                                         boolean isNonceStale) {

        // Get the realm name
        String realmName = config.getRealmName();
        if (realmName == null)
            realmName = REALM_NAME;

        String authenticateHeader;
        if (isNonceStale) {
            authenticateHeader = "Digest realm=\"" + realmName + "\", " +
            "qop=\"" + QOP + "\", nonce=\"" + nonce + "\", " + "opaque=\"" +
            getOpaque() + "\", stale=true";
        } else {
            authenticateHeader = "Digest realm=\"" + realmName + "\", " +
            "qop=\"" + QOP + "\", nonce=\"" + nonce + "\", " + "opaque=\"" +
            getOpaque() + "\"";
        }

        response.setHeader("WWW-Authenticate", authenticateHeader);

    }


    // ------------------------------------------------------- Lifecycle Methods
    
    @Override
    public void start() throws LifecycleException {
        super.start();
        
        // Generate a random secret key
        if (getKey() == null) {
            setKey(generateSessionId());
        }
        
        // Generate the opaque string the same way
        if (getOpaque() == null) {
            setOpaque(generateSessionId());
        }
        
        cnonces = new LinkedHashMap<String, DigestAuthenticator.NonceInfo>() {

            private static final long serialVersionUID = 1L;
            private static final long LOG_SUPPRESS_TIME = 5 * 60 * 1000;

            private long lastLog = 0;

            @Override
            protected boolean removeEldestEntry(
                    Map.Entry<String,NonceInfo> eldest) {
                // This is called from a sync so keep it simple
                long currentTime = System.currentTimeMillis();
                if (size() > getCnonceCacheSize()) {
                    if (lastLog < currentTime &&
                            currentTime - eldest.getValue().getTimestamp() <
                            getNonceValidity()) {
                        // Replay attack is possible
                        log.warn(sm.getString(
                                "digestAuthenticator.cacheRemove"));
                        lastLog = currentTime + LOG_SUPPRESS_TIME;
                    }
                    return true;
                }
                return false;
            }
        };
    }
 
    private static class DigestInfo {

        private String opaque;
        private long nonceValidity;
        private String key;
        private Map<String,NonceInfo> cnonces;
        private boolean validateUri = true;

        private String userName = null;
        private String method = null;
        private String uri = null;
        private String response = null;
        private String nonce = null;
        private String nc = null;
        private String cnonce = null;
        private String realmName = null;
        private String qop = null;

        private boolean nonceStale = false;


        public DigestInfo(String opaque, long nonceValidity, String key,
                Map<String,NonceInfo> cnonces, boolean validateUri) {
            this.opaque = opaque;
            this.nonceValidity = nonceValidity;
            this.key = key;
            this.cnonces = cnonces;
            this.validateUri = validateUri;
        }

        public boolean validate(Request request, String authorization,
                LoginConfig config) {
            // Validate the authorization credentials format
            if (authorization == null) {
                return false;
            }
            if (!authorization.startsWith("Digest ")) {
                return false;
            }
            authorization = authorization.substring(7).trim();

            // Bugzilla 37132: http://issues.apache.org/bugzilla/show_bug.cgi?id=37132
            String[] tokens = authorization.split(",(?=(?:[^\"]*\"[^\"]*\")+$)");

            method = request.getMethod();
            String opaque = null;

            for (int i = 0; i < tokens.length; i++) {
                String currentToken = tokens[i];
                if (currentToken.length() == 0)
                    continue;

                int equalSign = currentToken.indexOf('=');
                if (equalSign < 0) {
                    return false;
                }
                String currentTokenName =
                    currentToken.substring(0, equalSign).trim();
                String currentTokenValue =
                    currentToken.substring(equalSign + 1).trim();
                if ("username".equals(currentTokenName))
                    userName = removeQuotes(currentTokenValue);
                if ("realm".equals(currentTokenName))
                    realmName = removeQuotes(currentTokenValue, true);
                if ("nonce".equals(currentTokenName))
                    nonce = removeQuotes(currentTokenValue);
                if ("nc".equals(currentTokenName))
                    nc = removeQuotes(currentTokenValue);
                if ("cnonce".equals(currentTokenName))
                    cnonce = removeQuotes(currentTokenValue);
                if ("qop".equals(currentTokenName))
                    qop = removeQuotes(currentTokenValue);
                if ("uri".equals(currentTokenName))
                    uri = removeQuotes(currentTokenValue);
                if ("response".equals(currentTokenName))
                    response = removeQuotes(currentTokenValue);
                if ("opaque".equals(currentTokenName))
                    opaque = removeQuotes(currentTokenValue);
            }

            if ( (userName == null) || (realmName == null) || (nonce == null)
                 || (uri == null) || (response == null) ) {
                return false;
            }

            // Validate the URI - should match the request line sent by client
            if (validateUri) {
                String uriQuery;
                String query = request.getQueryString();
                if (query == null) {
                    uriQuery = request.getRequestURI();
                } else {
                    uriQuery = request.getRequestURI() + "?" + query;
                }
                if (!uri.equals(uriQuery)) {
                    return false;
                }
            }

            // Validate the Realm name
            String lcRealm = config.getRealmName();
            if (lcRealm == null) {
                lcRealm = REALM_NAME;
            }
            if (!lcRealm.equals(realmName)) {
                return false;
            }
            
            // Validate the opaque string
            if (!this.opaque.equals(opaque)) {
                return false;
            }

            // Validate nonce
            int i = nonce.indexOf(":");
            if (i < 0 || (i + 1) == nonce.length()) {
                return false;
            }
            long nonceTime;
            try {
                nonceTime = Long.parseLong(nonce.substring(0, i));
            } catch (NumberFormatException nfe) {
                return false;
            }
            String md5clientIpTimeKey = nonce.substring(i + 1);
            long currentTime = System.currentTimeMillis();
            if ((currentTime - nonceTime) > nonceValidity) {
                nonceStale = true;
                return false;
            }
            String serverIpTimeKey =
                request.getRemoteAddr() + ":" + nonceTime + ":" + key;
            byte[] buffer = null;
            synchronized (md5Helper) {
                buffer = md5Helper.digest(serverIpTimeKey.getBytes());
            }
            String md5ServerIpTimeKey = md5Encoder.encode(buffer);
            if (!md5ServerIpTimeKey.equals(md5clientIpTimeKey)) {
                return false;
            }

            // Validate qop
            if (qop != null && !QOP.equals(qop)) {
                return false;
            }

            // Validate cnonce and nc
            // Check if presence of nc and nonce is consistent with presence of qop
            if (qop == null) {
                if (cnonce != null || nc != null) {
                    return false;
                }
            } else {
                if (cnonce == null || nc == null) {
                    return false;
                }
                if (nc.length() != 8) {
                    return false;
                }
                long count;
                try {
                    count = Long.parseLong(nc, 16);
                } catch (NumberFormatException nfe) {
                    return false;
                }
                NonceInfo info;
                synchronized (cnonces) {
                    info = cnonces.get(cnonce);
                }
                if (info == null) {
                    info = new NonceInfo();
                } else {
                    if (count <= info.getCount()) {
                        return false;
                    }
                }
                info.setCount(count);
                info.setTimestamp(currentTime);
                synchronized (cnonces) {
                    cnonces.put(cnonce, info);
                }
            }
            return true;
        }

        public boolean isNonceStale() {
            return nonceStale;
        }

        public Principal authenticate(Realm realm) {
            // Second MD5 digest used to calculate the digest :
            // MD5(Method + ":" + uri)
            String a2 = method + ":" + uri;

            byte[] buffer;
            synchronized (md5Helper) {
                buffer = md5Helper.digest(a2.getBytes());
            }
            String md5a2 = md5Encoder.encode(buffer);

            return realm.authenticate(userName, response, nonce, nc, cnonce,
                    qop, realmName, md5a2);
        }

    }

    private static class NonceInfo {
        private volatile long count;
        private volatile long timestamp;
        
        public void setCount(long l) {
            count = l;
        }
        
        public long getCount() {
            return count;
        }
        
        public void setTimestamp(long l) {
            timestamp = l;
        }
        
        public long getTimestamp() {
            return timestamp;
        }
    }
}
